All-Pairs Shortest Path

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  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  can be found in the Wolfram Language using GraphDistanceMatrix[g], and a shortest path between two vertices  and  using FindShortestPath[g, u, v].

---

REFERENCES

Pemmaraju, S. and Skiena, S. "All-Pairs Shortest Paths." §8.1.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, pp. 330-331, 2003.

Skiena, S. "All Pairs Shortest Paths." §6.1.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 228-229, 1990.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength