全源最短路徑問題（all-pairs shortest path）
單源問的是從一個城市到各處最便宜的路線。全源問更完整的問題：每一對城市之間最便宜的路線。想像建一張完整的里程表，就像有時印在公路地圖冊背面的那種——一個格子，第 i 列第 j 行的條目是從城市 i 到城市 j 的最短距離。全源最短路徑就是填滿整張表的問題。
形式上，給定 V 個頂點的加權圖，對每個有序對 (i, j) 算出 dist(i, j)：從 i 到 j 任一路徑的最小邊權總和。輸出是一個 V 乘 V 的矩陣。一個顯而易見的做法是以每個頂點當源點各跑一次單源演算法——V 次獨立執行。在非負權重下這意味跑 V 次戴克斯特拉，成本約 O(V * (E + V log V))。在負權重下你得跑 V 次貝爾曼-福特，沉重的 O(V^2 * E)。專用的全源演算法勝過天真的重複：弗洛伊德-沃舍爾用優美而簡潔的程式碼，直接在 O(V^3) 內填滿矩陣；約翰森演算法則先把圖重新賦權一次，使它即使有負邊也能接著跑 V 次快速的戴克斯特拉。
全源距離支援任何需要一次比較眾多路線之事：對重複查詢預先計算的查表、全網路延遲圖、計算圖的直徑，以及依最短路徑距離做分群。誠實的取捨是成本。輸出 V^2 個距離意味光是寫出答案就絕不可能快過 O(V^2)，而實用方法落在 O(V^3) 區間，所以全源對數百到幾千個頂點的圖可行，而非數百萬。對兩個特定城市之間的單一路線，不要去解全源——改跑一次單源查詢。
對一個四城市的圖，答案是一張 4x4 的表，第 i 列第 j 行為 dist(i, j)；對角線為 0（城市到自身）。要在只有非負權重的圖上得到此表，跑四次戴克斯特拉，每個源點一次。在有些負邊的圖上，弗洛伊德-沃舍爾或約翰森填滿同一張表並正確處理負值。
全源產生一張完整的 V 乘 V 距離表；輸出它不可能快過 O(V^2)，而常用方法花 O(V^3)。
別為了回答單一個源點到目標的查詢而跑全源演算法——那極度浪費。全源唯有在你將對整張圖發出大量距離查詢時才划算。