所有點對最短路徑問題是指確定給定圖中每對頂點之間最短的圖距離。該問題可以使用
次Dijkstra演算法的應用來解決，或者使用Floyd-Warshall演算法一次性解決。後一種演算法也適用於邊具有負權重的加權圖。
所有頂點對之間距離的矩陣稱為圖距離矩陣，有時也稱為所有點對最短路徑矩陣。
圖
的圖距離矩陣可以在Wolfram 語言中使用以下方法找到GraphDistanceMatrix[g]，以及使用以下方法找到兩個頂點
和
之間的最短路徑FindShortestPath[g, u, v].
所有點對最短路徑
另請參閱
Bellman-Ford 演算法, Dijkstra 演算法, Floyd-Warshall 演算法, 圖距離, 圖距離矩陣, 圖測地線, 最短路徑問題使用 探索
參考文獻
Pemmaraju, S. 和 Skiena, S. “所有點對最短路徑。” 計算離散數學：組合數學和圖論與 Mathematica。 第 8.1.2 節。英國劍橋：劍橋大學出版社，第 330-331 頁，2003 年。Skiena, S. “所有點對最短路徑。” 實現離散數學：組合數學和圖論與 Mathematica。 第 6.1.2 節。馬薩諸塞州雷丁：Addison-Wesley，第 228-229 頁，1990 年。在 上被引用
所有點對最短路徑請引用為
Weisstein, Eric W. “所有點對最短路徑。” 來自 Web 資源。 https://mathworld.tw/All-PairsShortestPath.html