はむ吉(のんびり)の練習ノート

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

単一始点最短経路問題を解くShortest Path Faster AlgorithmをPython 3で実装してみた

グラフ理論における単一始点最短経路問題を解くアルゴリズムとしてはDijkstra法やBellman-Ford法が挙げられますが、Shortest Path Faster Algorithm (SPFA)もそのようなアルゴリズムの一つです。この記事では、SPFAの概要について述べるとともに、そのPython 3による実装をSingle Source Shortest Path (Negative Edges) | Aizu Online Judgeに対する解答例として示します。

きっかけ

yukicoderのとある問題*1の解説において、単一始点最短経路問題を解くアルゴリズムとしてSPFAが挙げられていました。これを受けて、軽く調べてみたところ、SPFAは競技プログラミングで時々使われる技法であることがわかりました。そこで、自分でもこれを実装してみることにしました。C++による実装は容易に見つかった*2ので、私がよく使うPython 3で書いてみました。

SPFAの概要

wikipedia:en:Shortest Path Faster Algorithmによると、SPFAはBellman-Ford法を改良したものであるといいます。あるいは、幅優先探索を無理やり拡張したものであるともいえるようです*3wikipedia:en:Shortest Path Faster Algorithmでは、ランダムな疎グラフに対してよく動作し、負の重みをもつ辺を含むグラフにとりわけ適したアルゴリズムであると述べられています。SPFAの最悪計算量は、Bellman-Ford法と同じO(|V||E|)です*4。また、以下で述べるように、負閉路の検出にも利用できます。

Python 3によるSPFAの実装例:AOJ GRL 1 Bの解答として

次に示すコードは、wikipedia:en:Shortest Path Faster Algorithm擬似コードに基づいて、私がSPFAをPython 3で実装したものです。これはSingle Source Shortest Path (Negative Edges) | Aizu Online Judgeへの解答でもあります。負閉路の検出はpath - Detecting negative cycles using SPFA algorithm - Stack Overflowを参考にして実装しました。

以下のコードでは、例外をわざわざ定義して、負閉路を見つけた際にそれを送出していますが、競技プログラミングで用いる場合には単なるassertで済ませてもよいかもしれません。また、collections.defaultdictを多用していますが、これは配列の初期化の手間を省くためです。


関連サイト・記事

SPFAについて調べていたところ、次のサイトを見つけました。このサイトでは、競技プログラミングで多用されるアルゴリズムC++による実装が、簡潔な説明とともにまとめられています。まだ全てには目を通せていませんが、勉強になります。
tubo28.me

次の記事はAtCoderの過去問について私が以前書いたものですが、単一始点最短経路問題・全点対最短経路問題の概要と、それらを解くための代表的アルゴリズム(Bellman-Ford法、Dijkstra法、ならびにWarshall-Floyd法)の特徴および実装に関する大まかな説明が含まれています。
hamukichi.hatenablog.jp

雑感

私は少しずつグラフに関するアルゴリズムを学んでいますが、それによって以前よりも解けそうな競技プログラミングの問題の数がかなり増えたように思います。多くの事柄がグラフとしてとらえられることを改めて実感しました。今回学んだSPFAも、ぜひ身につけたいと考えています。ただ、最近グラフに関する問題ばかり解いている気がするので、ほかの分野についても学習するように気を付けたいものです。また、問題を解く際には、有名なアルゴリズムだけで何とかしようとするのではなく、自分なりの考察をしっかりと行う必要があると感じています。