符號表示
| 資料 | ||
|---|---|---|
 | 從起點到各節點的暫定最短距離 | dist |
 | 最短路徑樹中的父節點 | parent |
 | 節點間的距離 | weight |
| 決定起點與初始化 | ||
|---|---|---|
 | 將起點的距離初始化為 0。 | dist[s] ← 0 |
 | 將其餘節點的暫定距離初始化為極大的值。 | dist[v] ← INF |
| 建立最短路徑樹 | ||
 | 尋找暫定距離最小的節點。 | # find minimum |
 | 指向擁有最小暫定距離的節點。 | u |
 | 更新節點的暫定距離與父節點。 | if dist[v] > dist[u] + weight[u][v]: dist[v] ← dist[u] + weight[u][v] parent[v] ← u |
 | 標示最短路徑樹暫定要使用的邊。 | (v, parent[v]) |
 | 擴大最短路徑樹。 | 將 u 新增至 T 內 |
| 輸出最短路徑樹 | ||
 | 利用父節點的資訊建立最短路徑樹。 | |
演算法動畫
決定起點與初始化
建立最短路徑樹
輸出最短路徑樹