Can Bellman-Ford algorithm be used to find shorthest path on a graph with only positive edges?

276 views Asked by At

I know that Dijkstra's algorithm can be used only on positive lengths of edges, and Bellman-Ford can be used when the graph also has negative ones.

Suppose we have a graph with only positive edges, though. Will Bellman-Ford give the same results as Dijkstra?

2

There are 2 answers

0
Ami Tavory On BEST ANSWER

Yes, it will give the same results. It will run slower, though, as it could also have been used for graphs with negative edges (subject to the absence of negative cycles). If you look at the proof of BF's correctness, there is no assumption there that some of the edges are negative.

0
AudioBubble On

I want to add something to Ami Tavory's answer. Bellman-ford's algorithm can be made a little bit faster if you can detect that on any pass, there is no node value update, then return from there. If there is no node update then it proves that every node traversal is complete.