NDO::Weblog

アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。

• http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt

SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。

単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というのがアルゴリズムの基本です。

24章ではベルマン・フォードのアルゴリズム、閉路なし有向グラフをトポロジカルソートを用いて高速に解く手法、ダイクストラのアルゴリズムの3つが紹介されていて、それぞれ頂点を調べる順序、緩和する回数が異なることから汎用性や効率性に差異があります。おまけ的に語られる、線形計画問題の特殊ケース (差分制約式系) を単一始点最短路問題に帰着させる話も面白かったです。

アルゴリズムイントロダクション輪講は最終回まで残すところあと2回です。