nodes in the original graph. The algorithm concludes by applying Dijkstra's algorithm to each of the four starting nodes in the reweighted graph. Correctness In the reweighted graph, all paths between a pair and of nodes have the same quantity added to them. The previous statement can be proven as follows: Let be an path. Its weight W in the reweighted graph is given by the following expression: Every is cancelled by in the previous bracketed expression; therefore, we are left with the following expression for W: The bracketed expression is the weight of p in the original weighting. Since the reweighting adds the same amount to the weight of every path, a path is a shortest path in the original weighting if and only if it is a shortest path after reweighting. The weight of edges that belong to a shortest path from q to any node is zero, and therefore the lengths of the shortest paths from q to every node become zero in the reweighted graph; however, they still remain shortest paths. Therefore, there can be no negative edges: if edge uv had a negative weight after the reweighting, then the zero-length path from q to u together with this edge would form a negative-length path from q to v, contradicting the fact that all vertices have zero distance from q. The non-existence of negative edges ensures the optimality of the paths found by Dijkstra's algorithm. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation. Analysis The time complexity of this algorithm, using Fibonacci heaps in the implementation of Dijkstra's algorithm, is : the algorithm uses time for the Bellman–Ford stage of the algorithm, and for each of the instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the Floyd–Warshall algorithm, which solves the same problem in time . References External links Boost: All Pairs Shortest Paths Graph algorithms Search algorithms Graph distance