The best shortest path algorithm
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
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).