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]+
.
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:
,
" in that order. e.g. a, b, 10
source
vertex you enter must be present in the graph.:
in these circles. These digits represent the vertex's minimum distance from the source.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)
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.