先日Twitterで少し話題になったので書いてみます。データ構造とアルゴリズム Advent Calendar 2018 の8日目の記事でもあります。 「01-BFS」というものをちょっと丁寧に解説します。これは以下のような問題を解くことができるアルゴリズムです。 辺の長さが0または1である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。 ※図のグラフは非循環(DAG)ですが、必ずしもDAGである必要はないです。 この記事では01-BFSの解説の前に「ダイクストラ法」「幅優先探索」をそれぞれ復習し、その流れで01-BFSを解説します。必須ではありませんが、これら2つのコードを書いたことがない人は是非そちらからやってみてください。 ダイクストラ法 多くの人は 深さ/幅優先探索→ダイクストラ法 の順に学ぶと思いますが、今回は逆の記載順にしています。 ダイ