Algorithm

最短経路と最小全域木

ダイクストラ法・ベルマン–フォード法・ワーシャル–フロイド法で最短経路を求め、クラスカル法とプリム法で最小全域木を作る方法をまとめます。

最短経路問題は、重み付きグラフで頂点から頂点へ向かう経路のうち、重みの合計が最小のものを求める問題です。最小全域木(MST)は、無向グラフのすべての頂点を閉路なしでつなぐ辺の集合のうち、重みの合計が最小のものです。この分野の中心となるアルゴリズムは、ダイクストラ法、ベルマン–フォード法、ワーシャル–フロイド法、0-1 BFS、クラスカル法、プリム法です。

これらのアルゴリズムは、地図アプリの経路探索、OSPF や RIP などのルーティングプロトコル、ゲームの経路探索、ケーブルや配管の設計、クラスタリングといった実際のシステムで使われています。コーディング面接や競技プログラミングでも定番です。問題をグラフとしてモデル化し、重みの性質(負の値があるか、0 と 1 だけか、疎か密か)に合ったアルゴリズムを選べるかが問われるからです。

まず BFS と優先度付きキュー(ヒープ)に慣れておきましょう。次に、すべての最短経路アルゴリズムに共通する緩和(relaxation)を理解し、小さなグラフでダイクストラ法を手でたどります。続いて負の辺があるとベルマン–フォード法が必要になる理由を確かめ、Union-Find を使うクラスカル法を実装し、最後に状態を拡張したグラフでダイクストラ法を動かす練習問題に取り組みます。