最短経路アルゴリズムの選び方

辺重みで分類する

辺重みがすべて 1 なら BFS を使う。重みが 0 と 1 だけなら deque を使う 0-1 BFS、すべて非負なら ダイクストラ法 を検討する。

負辺が存在する場合、ダイクストラ法の「確定した距離は後から短くならない」という前提が崩れる。Bellman–Ford 法、DAG 上の動的計画法、ポテンシャルによる重みの変換などから問題に合うものを選ぶ。

必要な距離で分類する

単一始点から全頂点への距離が必要なら、BFS やダイクストラ法を一度実行する。全頂点対の距離が必要で頂点数が小さければ Floyd–Warshall 法を検討する。

始点と終点が一つずつでも、途中の状態を頂点に含めることで状態空間上の最短経路として扱える場合がある。

実装前の確認

• グラフは有向か無向か
• 辺重みに負数があるか
• 距離の最大値が整数型に収まるか
• 到達不能な頂点をどう出力するか
• 経路そのものの復元が必要か

具体的な非負辺の実装は ダイクストラ法 を参照する。