最短経路

最短経路アルゴリズムは辺重みから選ぶ。すべての辺が同じコストなら BFS、重みが 0 または 1 なら 0-1 BFS、重みが非負なら ダイクストラ法 が候補になる。

選択手順と適用条件は 最短経路アルゴリズムの選び方 にまとめている。負辺がある場合はダイクストラ法を使えないため、Bellman–Ford 法や問題固有の変形を検討する。

実装時には、到達不能を表す値、距離の型、辺の向きを確認する。Python の優先度付きキューについては ヒープの使い方 を参照する。