The best shortest path algorithm

Question

What is the difference between the "Floyd-Warshall algorithm" and "Dijkstra's Algorithm", and which is the best for finding the shortest path in a graph?

I need to calculate the shortest path between all the pairs in a net and save the results to an array as follows:

**A     B     C     D      E**
A 0     10    15    5     20
B 10     0    5     5     10
C 15     5    0     10    15
D 5      5    10    0     15
E 20     10    15   15    0

Answer 1

Dijkstra's algorithm finds the shortest path between a node and every other node in the graph. You'd run it once for every node. Weights must be non-negative, so if necessary you have to normalise the values in the graph first.

Floyd-Warshall calculates the shortest routes between all pairs of nodes in a single run! Cycle weights must be non-negative, and the graph must be directed (your diagram is not).

Johnson's algorithm is using Dijkstra's algorithm to find all pairs in a single pass, and is faster for sparse trees (see the link for analysis).

Answer 2

Floyd Warshall find the paths between all pairs of vertices, but Dijkstra only finds the path from one vertex to all others.

Floyd Warshall is O(|V|³) and Dikstra is O(|E| + |V| log |V|) but you'll have to run it V times to find all pairs which gives a complexity of O(|E * V| + |V²| log |V|) I guess. This means it's possibly faster to use Dijsktra repeatedly than the FW algorithm, I would try both approaches and see which one is fastest in the actual case.

Answer 3

Dijkstra finds the shortest path from only one vertex, Floyd-Warshall finds it between all of them.

Answer 4

Use the Floyd-Warshall algorithm if you want to find the shortest path between all pairs of vertexes, as it has a (far) higher running time than Dijkstra's algorithm.

The Floyd-Warshall algorithm has a worst case performance of O(|V|³), where as Dijkstra's has a worse case performance of O(|E| + |V|log |V|)

Answer 5

Dijkstra's is mainly for single pair shortest path finding i.e. from one node to all other nodes, where as Floyd-Warshall is for all-pair shortest path i.e. shortest path between all pair of vertices. The Floyd-Warshall algorithm has a worst case performance of O(|V|3), where as Dijkstra's has a worse case performance of O(|E| + |V|log |V|) Also Dijkstra's cannot be used for negative weights ( we use Bellmann Ford for the same ). but for Floyd-Warshall we can use negative weights but no negative cycles

Answer 6

In the meanwhile better algorithms for the single source shortest path problem are known. A practically relevant one is a derivation of Dijkstra's algorithm by Torben Hagerup. The algorithm has the same worst case complexity as Djikstra's, but in the average case the expected runtime is linear in the size of the graph, which is much faster than the pure Dijkstra. The idea of the algorithm is based on the idea, that there is no need to always poll the minimum edge from the queue. It is possible poll an edge from the queue, whose weight is 1+k times as large as the minimum edge weight, where k is some number larger 0. Even if such an edge is chosen, the algorithm will still find the shortest path.