# How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

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?

• Bellman-Ford algorithm does not work on undirected graphs. Where do you find the assertion that "the Bellman-Ford algorithm needs only $n−1$ repetitions for both a directed and undirected graph"? Mar 6, 2019 at 17:12
• @kskxzr, this could be my point of confusion actually. I'm using the algorithm on an undirected graph of metro stations (vertices) and the connections between them (edges). I have a list of times from station A to B, with the implicit assumption that the time from B to A is the same, but only (A B time) is in the list. With each iteration of the Repeat(v-1 times) loop, I visit only the edges in my list. If Bellman-Ford only works for directed graphs, then I need to relax A and also B. Currently I'm only relaxing A, but I seem to still get the correct answer, which is worrisome. Mar 7, 2019 at 8:11
• Ahh, I found the problem. My program is only explicitly considering edge (A B), and relaxing only B. However, the list of edges (which I copied, not created from scratch), contains (A B time) and also (B A time). So effectively I'm relaxing both A and B. Thanks @kxkxzr for the comment, I helped me understand. Mar 7, 2019 at 8:28

The Bellman-Ford algorithm only needs $$n-1$$ iterations, regardless of the number of edges. The number of iterations needed depends only on the number of vertices, not on the number of edges.
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).