重み付きのグラフで、出発点から各頂点までの最短経路を求めるダイクストラ法の動きを、1回ずつたどれるツールです。辺と重みの一覧を書き換えると、図と手順の表がすぐに更新されます。カーナビの経路探索やネットワークのルーティング(OSPF)の基礎になる考え方を、試験の問題と同じ形の表で確かめられます。
お気に入りと最近使ったツールは、このブラウザ内（localStorage）にのみ保存されます。
今回確定した頂点 確定済み 今回の更新 最短経路
各回で確定した頂点(色付き)と、その時点での各頂点までの距離です。かっこの中は直前の頂点、赤字はその回に更新した距離で、確定済みの頂点は空欄にしています。
すべての頂点への最短距離:
重みが負の辺があると、ダイクストラ法では正しい答えが出ないことがあるため、重みは0以上に限っています。距離が同じ頂点が複数あるときは、名前の順で先の頂点を確定します。同じ2点の間に辺が複数あるときは、重みの小さいほうが使われます。
ほかの入力は今の値のまま、選んだ入力だけを今の値の1/4〜4倍の範囲で変えたときの結果です。赤い点が今の値です。
ダイクストラ法は、辺に0以上の重み(距離や時間、費用)が付いたグラフで、1つの出発点からすべての頂点への最短距離を求める方法です。まず出発点の距離を0、ほかの頂点を∞とします。次に、まだ確定していない頂点のうち距離が最小のものを選んで確定し、その頂点から辺でつながった未確定の頂点について「確定した頂点の距離 + 辺の重み」が今の距離より小さければ更新します。これを、すべての頂点が確定するまで繰り返します。例「6頂点の道路網」では、A→C→E→D→F が長さ20の最短経路になります。
辺の重みが0以上なら、未確定の頂点のうち距離が最小の頂点には、ほかの未確定の頂点を経由してもそれより短く着くことはできません。経由すると、そこまでの距離にさらに0以上の重みが足されるからです。このため、選んだ時点でその頂点の距離が最短だと確定できます。一方、重みが負の辺があるとこの理屈が成り立たないので、負の重みがあるグラフにはベルマン・フォード法などを使います。例「遠回りのほうが近い例」では、直接つながったSとTの辺(5)より、3本の辺をたどる経路(3)のほうが短いことを確かめられます。
頂点の数をV、辺の数をEとすると、未確定の頂点から最小のものを毎回探す素直な方法ではO(V²)、ヒープ(優先度付きキュー)を使うとO((V + E) log V)の計算量になります。カーナビや地図アプリの経路探索、ネットワークのルーティングプロトコルのOSPF(各ルータがリンクのコストからダイクストラ法で経路表を作る)、ゲームのキャラクターの移動経路などで使われています。地図のように大きなグラフでは、目的地の方向を見積もって探索を絞るA*(エースター)アルゴリズムなどの改良版も使われます。
試験では、手順の表を埋める問題や、ある頂点が何番目に確定するか、最短距離はいくつかを問う問題がよく出ます。表を作るときは、各回で「確定する頂点」と「更新される距離」を分けて書き、確定済みの頂点は以後変えないことに注意します。最短経路は、目的地から「直前の頂点」をさかのぼってたどります。このツールの表のかっこの中が直前の頂点です。
正解：B. S→B→A→C→T、長さ7
ダイクストラ法は、距離が確定していない頂点のうち最も近いものを確定し、その隣の頂点の距離を更新することを繰り返します。S(0)から B が1で確定し、B を通ると A は 1 + 2 = 3 で直接の4より短くなります。A(3)を確定すると C は 3 + 1 = 4、T は 3 + 6 = 9 になり、C(4)を確定すると T は 4 + 3 = 7 に更新されます。したがって最短経路は S→B→A→C→T で長さは7です。S→A→C→T(8)は S−A を直接通る分だけ長く、S→B→C→T(9)は B−C の5が大きいため長くなります。
正解：C. 辺の重みがすべて0以上であること
ダイクストラ法は、未確定の頂点のうち最も距離の小さいものを確定させます。これは、ほかの頂点を経由すると距離が増えることはあっても減ることはない、という前提に基づいています。負の重みの辺があると、後から別の経路で距離が短くなることがあり、例えば S→A が2、S→B が3、B→A が−2 の有向グラフでは、A を2で確定した後に S→B→A の1が見つかります。負の重みがあるときはベルマン・フォード法などを使います。閉路があっても、辺に向きがあっても、重みが0以上であればダイクストラ法は使えます。
正解：B. ルータどうしがルーティングプロトコルで経路の情報を交換し、障害で経路が使えなくなると自動的に別の経路に切り替える
静的ルーティングは、管理者が経路を手で設定する方法です。設定が単純で動きを予測しやすく、小さなネットワークや、出口が1つしかない拠点のデフォルトルートに向きますが、障害が起きても自動では切り替わりません。動的ルーティングでは、ルータがOSPFやBGPなどのルーティングプロトコルで情報を交換して経路表を自動で作り、リンクが切れると別の経路を計算し直します。インターネットでは、組織のネットワーク(自律システム)の間の経路をBGPで交換しています。実際のネットワークでは、両方を組み合わせて使うのが一般的です。
ダイクストラ法は使えないので、ベルマン・フォード法を使います。ベルマン・フォード法は、すべての辺で距離の更新を頂点の数−1回繰り返す方法で、計算量はO(VE)と大きくなりますが、負の重みを扱え、負の重みの閉路(回るほど距離が減る輪)も見つけられます。
すべての辺の重みが同じなら、幅優先探索(BFS)で辺の本数が最少の経路を求められます。ダイクストラ法は、重みが異なる場合にも使えるように、キューの代わりに距離の小さい順に取り出す優先度付きキューを使った幅優先探索の拡張と見ることができます。
出発点を変えてダイクストラ法を頂点の数だけ繰り返すか、ワーシャル・フロイド法を使います。ワーシャル・フロイド法は3重のループでO(V³)の計算量ですが、手順が簡単で、負の重みの辺(負の閉路がなければ)も扱えます。
OSPFは、ルータどうしがリンクの状態(つながりとコスト)を交換し、各ルータがネットワーク全体の地図を持って、ダイクストラ法で自分からの最短経路を計算するルーティングプロトコルです。例「ネットワークのルーティング」で、コストの合計が最小の経路が選ばれる様子を確かめられます。