The all-pairs shortest path problem is the determination of the shortest graph distances between every pair of vertices in a given graph. The problem can be solved using n applications of Dijkstra's algorithm or all at once using the Floyd-Warshall algorithm. The latter algorithm also works in the case of a weighted graph where the edges have negative weights. The matrix of all distances between pairs of vertices is called the graph distance matrix, or sometimes the all-pairs shortest path matrix. The graph distance matrix of a graph g can be found in the Wolfram Language using GraphDistanceMatrix[g], and a shortest path between two vertices u and v using FindShortestPath[g, u, v].

Bellman-Ford algorithm | Dijkstra's algorithm | Floyd-Warshall algorithm | graph distance | graph distance matrix | graph geodesic | shortest path problem