the best shortest path algoritm

Question

hello all,

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

thanks for your answers

Answer 1

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 2

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 3

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

Answer 4

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! 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).