All-Pairs Shortest Path
المؤلف:
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
الجزء والصفحة:
...
20-4-2022
2191
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
