所有点对最短路径问题是指确定给定图中每对顶点之间最短的图距离。该问题可以使用
次Dijkstra算法的应用来解决，或者使用Floyd-Warshall算法一次性解决。后一种算法也适用于边具有负权重的加权图。
所有顶点对之间距离的矩阵称为图距离矩阵，有时也称为所有点对最短路径矩阵。
图
的图距离矩阵可以在Wolfram 语言中使用以下方法找到GraphDistanceMatrix[g]，以及使用以下方法找到两个顶点
和
之间的最短路径FindShortestPath[g, u, v].
所有点对最短路径
另请参阅
Bellman-Ford 算法, Dijkstra 算法, Floyd-Warshall 算法, 图距离, 图距离矩阵, 图测地线, 最短路径问题使用 Wolfram|Alpha 探索
参考文献
Pemmaraju, S. 和 Skiena, S. “所有点对最短路径。” 计算离散数学：组合数学和图论与 Mathematica。 第 8.1.2 节。英国剑桥：剑桥大学出版社，第 330-331 页，2003 年。Skiena, S. “所有点对最短路径。” 实现离散数学：组合数学和图论与 Mathematica。 第 6.1.2 节。马萨诸塞州雷丁：Addison-Wesley，第 228-229 页，1990 年。在 Wolfram|Alpha 上被引用
所有点对最短路径请引用为
Weisstein, Eric W. “所有点对最短路径。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/All-PairsShortestPath.html