Create Graph

Enter each edge on a new line in the format: src, dest, weight.
src : [a-zA-Z0-9]+ . Case sensitive.
dest : [a-zA-Z0-9]+ . Case sensitive.
weight : -?[0-9]+ .

or select one of the default ones:

The Bellman-Ford algorithm computes shortest paths from a single source vertex to every other vertex in a weighted (,and in our case, directed) graph. Unlike the more popular Djikstra's algorithm, this algorithm is capable of finding shortest paths even in graphs with negative edge weights (but no negative weight cycles). The main idea is that the maximum length of the shortest path to any other vertex can be no more than |V| - 1 where |V|is the number of vertices in the graph. Therefore, if we relax all edges |V| - 1 times, we will end up with the shortest path from source to given vertices. NOTE: This implmentation does not detect the presence of negative cycles in the graph.

Read more about Bellman-Ford here:

  1. Create a new graph, or use one of the existing ones. To create a new graph,
    • Enter the edges of the graph in the text input box labeled "Edges". Each edge of the graph must be on a new line. An edge is represented by src, dest and weight seperated by "," in that order. e.g. a, b, 10
  2. Enter a source vertex. Bellman Ford will compute the shortest distance to every other vertex from the source vertex. The source vertex you enter must be present in the graph.
  3. Click the "Save" button. You should now see a graph corresponding to the edges you entered on the right side of this screen.
  4. Press the "Start" button. The "Next" button should now be enabled.
  5. Press the "Next" button to go through each step of Bellman-Ford's execution on this graph. The "Next" button will be disabled once you have gone through all the steps.
  6. Press the "Previous" button to go back a step. The "Previous" button will be disabled once you reach the start of execution.

Graph
  • Vertices are represented by opaque, solid circles. The text in a circle represents name of the vertex. If you've started execution of Bellman Ford, you may notice some digits to the right side of a : in these circles. These digits represent the vertex's minimum distance from the source.
  • A blue vertex represents the source node. A green vertex represents a vertex for which the minimum distance has just been updated.
  • Edges are presented by an arrow between two vertices. The number in the middle of an arrow represents the weight of that edge.
  • A yellow edge represents an edge that is currently being visited by the Bellman Ford algorithm. A green edge represents an edge for which a distance update has been accepted, i.e. for edge (u, v), old_dist(u) > dist(v) + w(u,v). A red edge represents an edge for which distance update was rejected, i.e old_dist(u) < dist(v) + w(u,v)

Parent Table
The parent table is left table with col names "node" and "parent". Assume a graph with an edge from node "u" to "v". If the shortest path to "v" includes the edge (u,v), then "u" is said to be the "parent" of "v". The values in this table change as we move through steps of the algorithm.

Distance Table
The distance table holds the value of minimum distance to a vertex from the source vertex. At any point, DistanceTable[u][iter] is the minimum distance from "source" to "u" at iteration number iter of Bellman-Ford. The values in this table change as we move through steps of the algorithm.

View this Project on GitHub.
© Created by Shashwat Rathod