3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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"? $\endgroup$
    – xskxzr
    Mar 6, 2019 at 17:12
  • $\begingroup$ @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. $\endgroup$
    – Jim Newton
    Mar 7, 2019 at 8:11
  • $\begingroup$ 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. $\endgroup$
    – Jim Newton
    Mar 7, 2019 at 8:28

2 Answers 2

Reset to default
2
$\begingroup$

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.

When you talk about converting a directed graph to an undirected graph, that conversion increases the number of edges but does not change the number of vertices. Thus, it doesn't change the number of iterations needed for the Bellman-Ford algorithm.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the insight. In fact, as mentioned above, an issue with any such implementation is that one must understand the semantics of his input data. My assumption (wrong) was that my data was explicitly directed, but had bi-directional semantics. My input data actually contains 2 edges for each pair of stations between which the metro commutes. However, there are some pairs of stations for which the metro only travels one direction; this is also reflected correctly in my input data. The moral: understand your data. $\endgroup$
    – Jim Newton
    Mar 7, 2019 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.