'Bellman-Ford vs. Dijkstra graph density
I was testing the two algorithms and Bellman-Ford performed better on sparse graphs and looking at the big-O analysis of both, O(VE) for Bellman-Ford and O(E + V lg V) for Dijkstra's. I believe this is correct. I did some researching that said
Dijkstra's is always faster and Bellman-Ford is only used when negative weight cycles are present.
Is that really the case?
Solution 1:[1]
TRUE.
Wikipedia: However, Dijkstra's algorithm greedily selects the minimum-weight node that has not yet been processed, and performs this relaxation process on all of its outgoing edges; in contrast, the Bellman–Ford algorithm simply relaxes all the edges, and does this |V | ? 1 times, where |V | is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra.
Bellman-Ford performs the check on all the vertices, Dijkstra only on the one with the best distance calculated so far. Again already noted, this improves the complexity of the Dijkstra approach, however it requires to compare all the vertices to find out the minimum distance value. Being this not necessary in the Bellman-Ford, it is easier to implement in a distributed environment. That's why it is used in Distance Vector routing protocols (e.g., RIP and IGRP), where mostly local information is used. To use Dijkstra in routing protocols, instead, it is necessary first to distribute the entire topology, and this is what happens in Link State protocols, such as OSPF and ISIS.
Solution 2:[2]
Asymptotically, for any graph where E ? V, the runtime of Dijkstra’s algorithm (O(E + V log V)) is smaller than that of Bellman-Ford (O(EV)). This means that, at least in theory, Dijkstra’s algorithm will outperform Bellman-Ford for large graphs of any density (assuming there’s at least as many edges as nodes). That’s borne out in practice, with Dijkstra’s algorithm usually running much faster.
Bellman-Ford is used, as you’ve mentioned, in cases where there are negative edges, which Dijkstra can’t handle. But there are other cases where Bellman-Ford is useful, too. For example, in network routing, where each network router needs to find shortest paths and there isn’t a central computer coordinating everything, the network routers can run a distributed version of Bellman-Ford to find shortest paths between computers due to how the computation only requires local updates to node distances. Dijkstra’s algorithm doesn’t work in this case.
There are also ways to improve the performance of Bellman-Ford in practice for many types of graphs. The Shortest Paths Faster Algorithm (SPFA) is a relatively simple optimization of Bellman-Ford that, while still retaining Bellman-Ford’s worst case runtime, is empirically faster in practice. Dijkstra’s algorithm, IIRC, is usually still faster than SPFA, but this does close the gap in some circumstances.
As you’ve mentioned
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Yongle Liu |
| Solution 2 | templatetypedef |