圖
最短路徑
最短路徑問題問的是：從一個頂點出發，把沿途經過的邊的權重加起來，到達另一個頂點最便宜的走法是什麼？這就是導航軟體為你規劃最快回家路線、網路選擇延遲最低的路由、遊戲角色尋找穿越地形最省代價路徑背後的數學。這裡的「最短」指總權重最小，並不總是邊數最少。
如果圖是無權的（每條邊都算作一步），答案就是邊數最少，而廣度優先搜尋已經能以 O(V + E) 解決它。一旦各條邊帶有不同權重，就需要一種總是優先考慮「當前已知最便宜前沿」的演算法。Dijkstra 演算法正是這樣做的：它逐步擴大一個最短距離已經確定的頂點集合，每次挑出尚未確定、暫定距離最小的那個頂點，並鬆弛它的出邊（若經由這個頂點更便宜，就更新鄰居的距離）。
Dijkstra 演算法假設邊權非負——一條負權邊會破壞它的貪婪推理，那種情況下需要換用別的方法，例如 Bellman-Ford。用優先佇列（二元堆積）實作時，Dijkstra 的執行時間約為 O((V + E) log V)，足以應付大型路網，是實務中應用最廣的單源最短路徑演算法。
// pq holds {distance, vertex}, smallest first
auto [d, v] = pq.top(); pq.pop();
if (d > dist[v]) continue; // stale entry
for (auto [nb, w] : adj[v])
if (dist[v] + w < dist[nb]) {
dist[nb] = dist[v] + w;
pq.push({dist[nb], nb});
}彈出最近的頂點，再改進任何經由它能更便宜到達的鄰居。
無權圖用 BFS，非負權用 Dijkstra，可能出現負權邊時用 Bellman-Ford。
又稱
另見