最短経路アルゴリズム(Shortest Path Algorithm)
1. 概要
A. 定義
最短経路アルゴリズム(Shortest Path Algorithm)とは、重みが付与されたグラフにおいて出発頂点と到着頂点を結ぶ複数の経路のうち、辺の重みの総和が最小となる経路を見つけるアルゴリズムの総称であり、単一始点(Single-Source)・単一対(Single-Pair)・全対(All-Pairs)問題に区分され、グリーディ(Greedy)と動的計画法(DP)という二つの設計戦略の上に実装される。
最短経路問題は「AからBへ行く最も安い道は何か」という普遍的な問いの数学的抽象化である。ここで「安さ」は距離・時間・費用・遅延・信頼性などどのような尺度でもよく、地図・道路網・通信網・工程フローを頂点(node)と重み付き辺(weighted edge)でモデル化すれば同一のアルゴリズムで解ける。ナビゲーションの経路案内、インターネットルーティングプロトコルの経路決定、ゲームキャラクタの移動、物流配送最適化がすべてこの一つの問題の変形であるという点で、最短経路はグラフ理論において最も実用的価値の大きいテーマに数えられる。
最短経路アルゴリズムの核心原理は最適部分構造(optimal substructure)と緩和(relaxation)である。最適部分構造とは「出発点から到着点までの最短経路に含まれる任意の中間区間もそれ自体で最短経路である」という性質で、大きな問題の解が小さな問題の解で構成されることを意味する。緩和とは現在までに判明している到着頂点までの距離推定値を「より短い経路が発見されれば更新する」演算で、すべての最短経路アルゴリズムは結局、緩和をどの順序で、何回行うかで区別される。この二つの原理がグリーディ(一度確定すれば後戻りしない)とDP(すべての場合を体系的に更新する)という相異なる戦略で実装されることで、アルゴリズムごとの特性と制約が分かれる。
B. 登場背景と必要性
重みのないグラフであれば幅優先探索(BFS)だけで辺数基準の最短経路を求められる。しかし現実の接続網は区間ごとに距離・所要時間・通行料・回線遅延がそれぞれ異なり、重みが必ず必要である。単に経由する頂点数が少ないから速い道というわけではなく、辺一つが他の数十個の辺の総和より大きいことがあるためである。この点でBFSは限界を露呈し、重みを考慮して累積コストを比較・緩和する専用アルゴリズムが要求される。
また現実の問題は重みの性質と問い合わせの形態が多様で、単一のアルゴリズムですべてをカバーできない。道路網のようにすべての重みが正の場合もあるが、為替裁定取引や補助金を含むコスト網のように負(−)の重みが存在する場合もある。一つの出発点からすべての目的地までを一度に求めねばならないときもあれば、すべての頂点対間の距離をあらかじめ計算しておかねばならないときもある。このように「負の辺の許容可否、負の閉路検出の必要性、問い合わせが単一始点か全対か、グラフが疎か密か」によって適切なアルゴリズムが変わるため、技術士は問題の条件を正確に識別し、Dijkstra・Bellman-Ford・Floyd-Warshall・A</strong>*のうち正しい道具を選ぶ眼識を備えねばならない。
2. 最短経路問題の分類と緩和原理
最短経路問題は問い合わせ範囲によって三類型に分かれる。単一始点最短経路(SSSP)は一つの出発頂点から残りすべての頂点までの最短距離を求め、Dijkstra・Bellman-Fordが代表的である。単一対最短経路は特定の出発-到着一対のみを要求するが、汎用解法がSSSPと同一であるため通常はSSSPを解きつつ目的地に到達すれば終了するか、A*で目的地方向のみを集中探索する。全対最短経路(APSP)はすべての頂点対の間の距離を求め、Floyd-Warshallが典型である。
flowchart TB
ROOT["最短経路アルゴリズム"] --> SSSP["単一始点 (SSSP)"]
ROOT --> APSP["全対 (APSP)"]
SSSP --> DIJ["Dijkstra (グリーディ、負の辺不可)"]
SSSP --> BF["Bellman-Ford (DP、負の辺・閉路検出)"]
SSSP --> ASTAR["A* (ヒューリスティックに基づく目的地集中)"]
APSP --> FW["Floyd-Warshall (DP、全対)"]
APSP --> JOHN["Johnson (疎グラフ向けAPSP)"]
この分類に加えて、重みがまったくない(あるいはすべての辺が同一コストの)グラフであれば、上記のアルゴリズムはそもそも不要である点も押さえるべきである。その場合幅優先探索(BFS)が辺数基準の最短経路をO(V+E)で提供するため、重み付きアルゴリズムは「辺ごとにコストが異なるとき」に初めて正当化される。実務では「距離1の辺と重み付き辺が混在する」変形(0-1 BFS、Dijkstra縮約)も登場するが、問題の重み構造を正確に把握し、最も単純でありながら正しい道具を選ぶことが過剰設計を避ける出発点である。
すべてのアルゴリズムを貫く共通演算が緩和(Edge Relaxation)である。各頂点vは出発点からの暫定最短距離dist[v]を持ち、初期には出発点のみ0、残りは無限大(∞)とする。辺(u, v)の重みをwとするとき、緩和は「dist[u] + w < dist[v]ならばdist[v]をdist[u] + wに縮め、vの先行者をuとして記録する」単純な比較-更新である。先行者を併せて記録しておけば到着後に逆追跡で実際の経路まで復元できる。結局Dijkstraは「距離が確定した頂点を一つずつ増やしながらその周辺のみを緩和する」グリーディ順序であり、Bellman-Fordは「すべての辺をV−1回反復緩和する」全数的順序であり、Floyd-Warshallは「経由可能な中間頂点を一つずつ増やしながら全対を緩和する」DP順序であるという点で、三つのアルゴリズムは同一の緩和を異なるスケジュールで行う変奏として理解できる。
flowchart LR
U["頂点 u: dist=5"] -- "w=3" --> V["頂点 v: dist=10"]
V --> CHK{"dist[u]+w = 8 は dist[v] = 10 より小さいか?"}
CHK -->|"はい"| UPD["dist[v]=8, prev[v]=u に更新"]
CHK -->|"いいえ"| KEEP["更新なし、既存経路を維持"]
3. グリーディ基盤: Dijkstraアルゴリズム
Dijkstraアルゴリズムは1959年にエドガー・ダイクストラが提案した単一始点最短経路アルゴリズムで、すべての辺の重みが非負(0以上)のグラフで動作する。核心戦略はグリーディである。「まだ確定していない頂点のうち出発点からの暫定距離が最も短い頂点を一つ選んでその距離を確定し、その頂点に隣接する辺を緩和する」過程をすべての頂点が確定するまで反復する。
このグリーディ選択が正しい理由は非負の重みという前提にある。現在未確定の頂点のうち暫定距離が最小の頂点uを考えると、uへより短く到達する別経路があるには、その経路はuより暫定距離の大きいある頂点を必ず経由せねばならない。ところが辺の重みが負でないので、より遠い頂点を経由してuへ戻れば距離は決して縮まらない。したがってuの現在の暫定距離はすでに最終最短距離であり、一度確定した頂点は再度更新する必要がない。まさにこの「後戻りしない」ことがグリーディの効率を生むが、同時に負の辺に出会うと前提が崩れて誤答を出す致命的限界の根源でもある。負の辺があれば「より遠く回り道してから負の辺で距離を縮める」経路が可能になり、すでに確定した値が誤りになりうるためである。
負の辺でDijkstraがなぜ誤るかは簡単な反例で確認される。頂点S·A·Bで辺がS→A=1、S→B=4、A→B=−3としよう。Dijkstraは第一段階でSを確定した後、暫定距離のより小さいA(1)をB(4)より先に確定しようとするが、その前にBの暫定距離はdist[B]=4に設定される。その後Aを確定しA→Bを緩和すれば1+(−3)=−2でBが更新されるべきだが、もしBがAより先に確定される順序であればこのより短い経路を見逃す。実際により複雑なグラフでは「すでに確定してしまった頂点」を負の辺が後からさらに縮める状況が生じて確定値が誤りになり、これがDijkstraに負の辺を絶対に使ってはならない根本理由である。なお「いっそすべての重みに大きな定数を足して正にすればよいのではないか」という発想は、経路ごとに含まれる辺数が異なり足される定数量が異なるため最短経路の順位を変えてしまい正しくない。
具体的な動作を小さな例で追ってみよう。頂点S(出発)·A·B·C·T(到着)があり、辺がS→A=4、S→B=1、B→A=2、B→C=5、A→C=1、C→T=3のときを考える。最初はdist[S]=0、残りは∞である。第一段階で暫定距離が最小のS(0)を確定しSの辺を緩和すればdist[A]=4、dist[B]=1となる。次に未確定のうち最小のB(1)を確定し緩和すれば、B→Aで1+2=3 < 4であるためdist[A]=3に縮まり、B→Cでdist[C]=6となる。続いてA(3)を確定しA→Cで3+1=4 < 6であるためdist[C]=4に更新される。その次にC(4)を確定しC→Tでdist[T]=7を得て、最後のT(7)を確定すれば終了する。最短経路は先行者配列を逆追跡してS→B→A→C→T(コスト7)に復元される。この例に見るように、一度確定した頂点(S·B·A·C)はその後決して再び縮まることがなく、この不変式がグリーディの正当性を支える。
性能は未確定の頂点のうち最小距離頂点を見つけるデータ構造に左右される。単純な配列で毎回線形探索すればO(V²)であり、優先度付きキュー(最小ヒープ、Min-Heap)を使えば緩和ごとの距離更新をO(log V)で処理し全体をO((V + E) log V)に改善する。頂点は多いが辺が少ない疎グラフ(sparse graph)ではヒープ基盤が大きく有利であり、辺が頂点の二乗に近い密グラフ(dense graph)では単純な配列がむしろ良いことがある。フィボナッチヒープを使えば理論上O(E + V log V)まで下がるが定数が大きく、実務では二分ヒープが標準である。ヒープ基盤の実装では一つの頂点が複数回キューに入りうるが、すでに確定した頂点がキューから再び取り出されれば読み飛ばす「遅延削除(lazy deletion)」方式が実装が簡単で広く使われる。
代表的な産業適用はOSPF(Open Shortest Path First)ルーティングプロトコルである。OSPFはリンク状態(Link-State)方式で各ルータが全ネットワークトポロジを共有した後、自身をルートにDijkstra(SPF、Shortest Path First)を回して目的地別の最適経路を計算する。たとえば回線帯域をコスト(cost)に換算し1Gbpsリンクより100Mbpsリンクのコストを高く付ければ、Dijkstraが帯域の大きい経路を自然に選好するようにできる。ナビゲーションも道路区間の所要時間を重みに置いてDijkstra系統を適用するが、全国道路網は頂点が数千万個であり純粋なDijkstraでは遅いため、後述するA*や前処理技法で加速する。
4. 動的計画法基盤: Bellman-FordとFloyd-Warshall
Bellman-FordアルゴリズムはDijkstraが諦めた負の辺を許容する。戦略は全数的である。「グラフのすべての辺を一度ずつ緩和する作業をV−1回反復」する。最短経路は閉路を含まないので最大V−1個の辺から成るが、各反復(パス)ごとに最短経路の辺が最低一つずつ確定的に緩和されるため、V−1回ですべての最短距離が収束する。時間計算量はO(V·E)でDijkstraより遅いが、後戻りしないグリーディと異なりすべての辺を反復緩和するため、負の辺が割り込んでも正しい答えを得る。
なぜV−1回で十分かは緩和の伝播速度で理解できる。1回目のパスを終えると出発点から辺1個で到達するすべての頂点の最短距離が確定し、2回目のパスを終えると辺2個で到達する経路が確定する、という具合に、k回目のパスは「辺を最大k個使う最短経路」を保証する。いかなる最短経路も辺V−1個を超えないので、V−1回のパスで全体が収束する。これはDijkstraが「頂点を距離順に一個ずつ確定する」のと異なり、Bellman-Fordが「経路長(辺数)を一層ずつ広げる」DPであることを示す。ただし辺の緩和順序が良ければV−1回よりはるかに早く収束するため、一つのパスで何の更新も起きなければ直ちに終了する早期終了(early termination)最適化がよく使われる。
Bellman-Fordのもう一つの決定的価値は負の閉路(negative cycle)検出である。V−1回反復後にもう一度(V回目)辺を緩和したとき、依然として距離が縮まる辺が存在すれば、回るほどコストが減少する負の閉路があるという意味である。この場合最短経路が負の無限大に発散して定義されないため、アルゴリズムはこれを報告する。この性質は為替裁定取引(arbitrage)検出に直接応用される——通貨を頂点、為替レートの負の対数を辺の重みに置けば、負の閉路の存在がすなわち「一周回って利益が残る取引機会」を意味する。ルーティングではRIP(Routing Information Protocol)が距離ベクトル(Distance-Vector)方式でBellman-Ford原理を分散適用するが、隣接ルータ同士のみ経路情報をやり取りするため収束が遅く「無限カウント(count-to-infinity)」問題があり、ホップ数を15に制限するなど小規模網に限られる。
RIPの距離ベクトル方式をもう少し覗くとBellman-Fordの分散的性格が現れる。各ルータは全体の地図を知らないまま「直接接続された隣接ルータが知らせた目的地別距離に、自身と隣接ルータの間のコストを足した値」で自身の経路表を更新する。これはBellman-Fordの緩和をネットワーク全体に分散して反復実行するのと同じである。問題はリンクが切れたときに「隣接ルータがまだ知らない古い経路を再び参照する」ことで距離が徐々に無限大へ跳ね上がる無限カウント(count-to-infinity)現象であり、これを緩和するためホップ数上限(15)、水平分割(split horizon)、ルートポイズニングのような補完技法が使われる。このように理論アルゴリズムが分散・動的環境に置かれると収束性という新たな課題が生じる点は、技術士の観点から重要な洞察である。
Floyd-Warshallアルゴリズムはすべての頂点対(APSP)間の最短距離を一度に求めるDP技法である。核心発想は「経由を許容する中間頂点の集合を一頂点ずつ広げること」である。k番目の段階では「頂点1..kのみを中間経由地に使えるとき」の全対(i, j)最短距離を求め、漸化式はdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])である。すなわち「kを経由しない既存経路」と「i→k→jでkを経由する経路」のうち短い方を選ぶ。三重ループで簡潔に実装され計算量はO(V³)である。負の辺を許容するが負の閉路がなくてはならず、対角成分dist[i][i]が負になれば負の閉路を検出したことになる。頂点数が数百規模で小さく全対距離が必要な場合(例: 小規模ネットワークの遅延行列、ゲームマップの事前計算)に特に適する。たとえば頂点が300個の社内ネットワークの全地点間遅延行列を求めるには、Dijkstraを300回反復(300×O((V+E)log V))するより、O(300³)=2,700万演算の三重ループ一回が実装も簡潔でキャッシュ局所性も良く実務上有利である。逆に数百万頂点の疎グラフでAPSPが必要ならFloyd-WarshallのV³は過度であるため、すべての頂点からDijkstraを回しつつ負の辺は再重み付け(reweighting)で除去するJohnsonアルゴリズムがより効率的である。
比較: どのアルゴリズムをいつ使うか
三つのアルゴリズムの選択は「負の辺の有無、問い合わせ範囲、グラフ密度」という三つの軸で整理される。下表はその違いを要約するが、違いが生じる理由は前節の設計原理に根ざす。
| 区分 | Dijkstra | Bellman-Ford | Floyd-Warshall |
|---|---|---|---|
| 設計戦略 | グリーディ | 動的計画法(辺反復) | 動的計画法(経由地拡張) |
| 問い合わせ範囲 | 単一始点 | 単一始点 | 全対 |
| 負の辺 | 不可 | 可能 | 可能(負の閉路がないとき) |
| 負の閉路検出 | 不可 | 可能 | 可能 |
| 時間計算量 | O((V+E)log V) | O(V·E) | O(V³) |
| 適合状況 | 正の重み大規模ルーティング | 負の辺・裁定取引・RIP | 小規模全対距離 |
実務的含意は明白である。道路網・OSPFのように重みが常に正で出発点一つから大規模に経路を取り出さねばならないならDijkstraが圧倒的に速い。一方コストに負が混じるか負の閉路自体が検出対象なら、遅くてもBellman-Fordを使わねばならない。頂点数が小さく全対距離が必要なら、実装が最も簡潔なFloyd-Warshallが良い。計算量だけを見てDijkstraを選んだ末に負の辺のせいで誤答を出すのは典型的な設計ミスであり、逆に正のグラフにFloyd-Warshallを使って不要にV³コストを払うのも過剰である。
三つのアルゴリズムの関係を一文で要約すれば、Dijkstraは「正のグラフに特化した速いグリーディ」、Bellman-Fordは「負まで扱う安全なDP」、Floyd-Warshallは「全対を一度に求める簡潔なDP」である。これらは競争関係というより問題条件によって役割が分かれる相互補完的な道具一式であり、実際のシステムはしばしばこれらを組み合わせる。たとえば大規模ルーティングシステムは普段はDijkstraで速く経路を取り出しつつ、政策上負に該当する報奨・割引の重みが導入されればその領域のみにBellman-Fordを適用する形のハイブリッド設計が可能である。
5. 深化: A*ヒューリスティック探索と大規模経路探索の加速
大規模リアルタイム経路探索では純粋なDijkstraも遅い。Dijkstraは目的地の方向と無関係に出発点を中心に四方へ距離を確定するため、目的地が片側にあっても反対側の頂点まで不要に探索する。**A*(A-star)アルゴリズムはここにヒューリスティック(heuristic)推定関数h(n)**を加えて「目的地に近く見える頂点を優先探索する」よう誘導する。A*は各頂点の優先度をf(n) = g(n) + h(n)で評価するが、g(n)は出発点からnまで実際に累積した距離、h(n)はnから目的地までの推定距離(例: 地図座標上の直線距離)である。h(n)が実際の距離を決して過大評価しない許容可能(admissible)条件を満たせば、A*はDijkstraと同一に最適解を保証しつつ探索範囲を目的地側に狭めてはるかに速い。h(n)=0とすればA*はちょうどDijkstraになるので、A*はDijkstraの一般化と見られる。
A*はゲームAIの経路探索(pathfinding)とロボット経路計画の事実上の標準である。格子(grid)マップでユニットを目標地点へ移動させるとき直線距離(ユークリッド)または格子距離(マンハッタン)をヒューリスティックに使えば、数百万マスのマップでも少数のノードのみ展開してリアルタイム移動が可能である。ただしヒューリスティックが過大評価すれば最適性を失い、ヒューリスティック計算自体が高価であれば利得が相殺されるため、h(n)の設計が性能を左右する。
ヒューリスティックの効果を数値で見積もってみよう。1,000×1,000格子マップで出発点と目的地がマップ両端にあるとするとき、Dijkstraは出発点を中心に同心円のように広がりながら数十万マスを確定しうる。一方マンハッタン距離をヒューリスティックに使うA*は目的地へ向かう狭い帯状にのみ探索を集中し、障害物の少ないマップでは経路長に比例する数千マス水準のみ展開しても同一の最適経路を見つける。障害物が多くヒューリスティックの「直線推定」が実際の迂回距離と大きくずれるほどA*の利点は減りDijkstraに近づくが、これはヒューリスティックの情報性(informedness)が高いほど探索が効率的であるという原理をよく示す。リアルタイム性が絶対のゲームでは完全な最適経路の代わりに「十分に良い」経路をより速く出すためヒューリスティックに重みを足した重みA*(Weighted A*)を使うこともあるが、これは最適性を一部譲って応答時間を買う典型的なトレードオフである。
全国単位ナビゲーションのように頂点が数千万個の道路網はA*だけでも不足で前処理基盤の加速を使う。代表的に縮約階層(Contraction Hierarchies)は重要度の低い頂点をあらかじめ除去しながらショートカット辺を追加して階層構造を作っておき、問い合わせ時に双方向探索でミリ秒以内に全国経路を算出する。もう一つの技法である双方向探索(bidirectional search)は出発点と到着点から同時に探索を進めて中間で出会わせることで、探索が広げる領域をおよそ半分以下に減らす——単方向が半径rの円を探索するなら双方向は半径r/2の二つの円を探索するわけで、面積が大きく減るためである。また実際のナビゲーションは交通量によって重みが頻繁に変わる動的重み環境であるため、リアルタイム交通情報を反映して周期的に距離を再計算するか影響を受ける区間のみ増分更新する技法が結合される。このように「静的最短経路アルゴリズム → ヒューリスティック → 前処理 → 動的更新」へ拡張される流れは、最短経路技術が教科書アルゴリズムを超えて持続発展する領域であることを示す。
6. 考慮事項および示唆点
最短経路アルゴリズムを技術士の観点から設計・適用する際は次を総合的に考慮せねばならない。
重みの性質をまず確定してからアルゴリズムを選ぶ。 すべての辺が正であればDijkstraが最善だが、負の辺が一つでもあればDijkstraは誤答を出すのでBellman-Ford・Floyd-Warshallへ転換せねばならない。要求分析段階で「コストに負が現れうるか、負の閉路検出が目的か」を必ず識別せねばならず、これを見落とすと正答に見える誤った結果を量産する。
問い合わせ範囲とグラフ密度によってデータ構造・計算量を調整する。 単一始点・疎グラフにはヒープ基盤Dijkstra(O((V+E)log V))、全対・小規模密グラフにはFloyd-Warshall(O(V³))、全対・大規模疎グラフにはJohnsonが適する。問い合わせが頻繁でグラフが静的なら前処理(縮約階層)コストをかけて問い合わせを加速する戦略が有効である。
実際の経路復元と同点(tie)処理を設計に含める。 距離値だけでなく先行者(prev)配列も併せて維持してこそ経路自体を逆追跡できる。また最短距離が同一の複数経路が存在するときどれを選ぶか(辺数最小、特定の優先度など)に対するタイブレーク規則を明示してこそ再現性のある結果を得る。
動的・分散環境の収束性と拡張性を考慮する。 ルーティングのようにトポロジ・重みが変わる環境では全体再計算コストと収束遅延が問題となる。リンク状態(OSPF、全域情報 + Dijkstra)は収束が速いが情報共有負荷が大きく、距離ベクトル(RIP、局所情報 + Bellman-Ford)は単純だが無限カウント・遅い収束のリスクがあるので、網規模と変動性に合わせて選択・混用せねばならない。
ヒューリスティックと近似のトレードオフを管理する。 A*のヒューリスティックは速度を大きく高めるが許容可能条件を違反すれば最適性を失う。超大規模・リアルタイム要求では最適解を少し譲って応答時間を確保する近似・前処理技法が合理的でありうるので、「正確性対応答性」のトレードオフをサービス要求水準(SLA)に合わせて調整する判断が必要である。
数値安定性と実装上の落とし穴を点検する。 無限大(∞)を非常に大きい整数で表現するとき緩和過程で
∞ + wオーバーフローが発生しないよう上限を設け、負の辺があるのにDijkstraを使う典型的な誤りやFloyd-Warshallの反復順序(kを最も外側のループに置かねばならない)を間違える失敗を警戒せねばならない。小さな実装上の誤りが「もっともらしいが誤った」経路を作り運用事故につながりうるので、境界事例(到達不可頂点、自己閉路、同一コスト多重経路)に対する検証を設計に含める。隣接するグラフ問題との連携を活用する。 最短経路は最小全域木(MST)、最大流(Max-Flow)、トポロジカルソートのような他のグラフ問題と設計原理を共有し、しばしば結合される。たとえばDAG(有向非巡回グラフ)ではトポロジカルソート順に一度だけ緩和しても負の辺を含めてO(V+E)で最短経路を求められるので、グラフの構造的特性を把握すれば汎用アルゴリズムより速い特化解法を適用できる。問題を最短経路に還元(reduction)して解くモデリング能力もまた重要である。
総合すると、最短経路アルゴリズムは緩和と最適部分構造という共通原理の上でグリーディ(Dijkstra)とDP(Bellman-Ford·Floyd-Warshall)に分かれ、ここにヒューリスティック(A*)と前処理・動的更新が加わり、ルーティング・ナビゲーション・ゲーム・物流全般を支える基盤技術である。技術士は問題の条件(重みの性質・問い合わせ範囲・グラフ規模・変動性)を正確に診断し、正確性・性能・拡張性の均衡点で正しいアルゴリズムと加速戦略を選択・組み合わせる力量を備えねばならない。
参考資料
- E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, 1959. https://link.springer.com/article/10.1007/BF01386390
- P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, 1968. https://ieeexplore.ieee.org/document/4082128
- RFC 2328, "OSPF Version 2". https://www.rfc-editor.org/rfc/rfc2328
- RFC 2453, "RIP Version 2". https://www.rfc-editor.org/rfc/rfc2453
一言まとめ: 最短経路アルゴリズムは緩和と最適部分構造を土台に、正のグラフの単一始点に強いグリーディDijkstra、負の辺・閉路を扱うDP Bellman-Ford、全対を求めるFloyd-Warshall、ヒューリスティックで目的地を集中探索するA*に分かれ、重みの性質・問い合わせ範囲・グラフ規模を診断して正確性と性能の均衡点で選択・加速することが核心である。