シンボル
| データ | ||
|---|---|---|
 | 始点から各ノードへの暫定最短距離 | 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]) |
 | 最短経路木を拡張していきます。 | Tにuを含める |
| 最短経路木を出力 | ||
 | 親の情報から最短経路木を構築します。 | |
アニメーション
始点の決定と初期化
最短経路木の構築
最短経路木を出力