patternMinor
How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs
Viewed 0 times
bellmantheiterationshowneedgraphsdirectedalgorithmfordundirected
Problem
The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$. Note that we don't relax $u$ and $v$ on each iteration through the edges.
What I don't understand is that if $G$ is an undirected graph with $n$ vertices, then it is equivalent to a directed graph with $2n$ vertices. We simply think of the edge between $u$ and $v$ as a set $\{u,v\}$ for an undirected graph, and as the ordered pair $(u,v)$ for a directed graph.
I don't understand why the Bellman-Ford algorithm needs only $n-1$ repetitions for both a directed and undirected graph. It seems like it should take $n-1$ repetitions for directed graph, and $2n-1$ repetitions for undirected graphs or we should relax both vertices of an edge on each iteration.
Otherwise stated, why does running Bellman-Ford on a directed graph, also find the shortest paths of the undirected graphs?
What I don't understand is that if $G$ is an undirected graph with $n$ vertices, then it is equivalent to a directed graph with $2n$ vertices. We simply think of the edge between $u$ and $v$ as a set $\{u,v\}$ for an undirected graph, and as the ordered pair $(u,v)$ for a directed graph.
I don't understand why the Bellman-Ford algorithm needs only $n-1$ repetitions for both a directed and undirected graph. It seems like it should take $n-1$ repetitions for directed graph, and $2n-1$ repetitions for undirected graphs or we should relax both vertices of an edge on each iteration.
Otherwise stated, why does running Bellman-Ford on a directed graph, also find the shortest paths of the undirected graphs?
Solution
The Bellman-Ford algorithm does not work on undirected graphs with negative weights, because $(u,v)$ and $(v,u)$ are not allowed on the same path, but the Bellman-Ford algorithm does not handle this constraint. In fact, if the weight of $(u,v)$ is negative, $(u,v)$ and $(v,u)$ form a negative cycle.
If your weights are all non-negative (which is possibly your case according to your comment), the Bellman-Ford algorithm can work on undirected graph. The reason why it requires only $n-1$ iterations is explained in D.W.'s answer. However, you may want to take the advantage of non-negative weights and use some more efficient algorithm (like Dijkstra's algorithm).
Otherwise you can use the technique of T-joins or perfect matching.
If your weights are all non-negative (which is possibly your case according to your comment), the Bellman-Ford algorithm can work on undirected graph. The reason why it requires only $n-1$ iterations is explained in D.W.'s answer. However, you may want to take the advantage of non-negative weights and use some more efficient algorithm (like Dijkstra's algorithm).
Otherwise you can use the technique of T-joins or perfect matching.
Context
StackExchange Computer Science Q#105212, answer score: 3
Revisions (0)
No revisions yet.