algorithmshortest-pathdijkstrabellman-fordlongest-path

Why can't Bellman-Ford be used for Single Source Longest Path?


Dijkstra's cannot be used for longest path because it uses the property that the current shortest path will be for sure shorter than one of the other paths. This is correct, of course, assuming there are no negative edge weights. This concept is also why longest path doesn't work on Dijkstra, because the current longest path doesn't guarantee that there won't be another longer path that takes a larger value later on.

On the other hand, Bellman Ford offers the the flexibility of negative weights at a worse performance. This means that for Bellman Ford, so it doesn't work on the same greedy property as Dijkstra. So that's why I'm confused - why can't Bellman Ford be used on the Single Source Longest Path problem(NP hard)? For example, we can simply multiply all the weights of a graph by -1 and find the shortest path, which would be the longest path of the original graph.


Solution

  • Bellman–Ford allows arcs to be reused (otherwise there would be a well defined shortest path even in the presence of negative cycles), whereas the Single Source Longest Path problem derives its NP-hardness from the fact that it does not (otherwise you could just use Bellman–Ford after multiplying all of the weights by −1).