The best shortest path algorithm

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

Solution 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.

Solution 3:

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

Solution 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|)