最長経路
与えられたグラフ$ G(V, E)について最短経路ではなく最長の経路を求める問題。よく知られていることだが、辺のコストが正の最短経路問題が多項式時間で解けるのに対して、辺のコストが正の最長経路問題はNP困難である(細かいが長さが$ K以上の経路を求める問題と言いかえれば、これはNP完全になる)。しかし、これは閉路があり、かつ負の辺があるグラフの最短経路問題でも同じことなので、最短経路か最長経路か、というよりも、閉路と負のコストの辺があるかどうかの問題であろう。 なお、ベルマン・フォード法を使った場合、閉路を検出した上で、解として求められている経路にその閉路が影響を及ぼすかどうか、言いかえると、得られた最長経路を無限大にすることが可能かどうか、判定する必要に迫られることが多い。たいていのベルマン・フォード法では$ N = |V|としたときに$ N-1回のループで最長経路候補を見つけ、その後、それが無限大になる可能性があるかどうかを調べる。
その際には、いくつかのやり方があるが、以下の2つが考えられる。
$ N - 1回以降もループを回し、最長経路が更新された頂点に印をつける。さらに、任意の辺の始点に印がついていたら終点にも印をつけて伝播させる、ということを$ N回繰り返して、いま注目している経路の終点に印がつくか調べる
すべての最長経路候補に含まれる頂点の集合を保持し、それらの$ 1つでも$ N-1回目以降のループで最長経路が更新されるか調べる。ループを$ N回まわせば、どれかの候補が無限大長になるかどうか判定できる。なお、すべての最長経路候補は始点および終点からの深さ優先探索で調べることができる。