幅優先探索 (重みなし)
計算量: O(|E| + |V|)
ダイクストラ法 (正の重みのみ)
計算量: O(|E|log|V|)
ベルマンフォード法 (負の重みも含む)
計算量: O(|E|×|V|)
ワーシャルフロイド法 (実装が簡単、負の閉路に気づけない)
計算量: O(V^3)
( V: 頂点集合 )
( E: 辺の集合 )
( Point ) 負の重みがある場合、ある点で最短でなくても、さらに進んだ点で最短となる場合がある。
(例) 重み -5 の場合、合計 -10 のアドバンテージ
最短経路なので何度同じ場所を通ってもよい