How to make a dijkstra longest path?

What is an intuitive explanation of Dijkstra's shortest path algorithm on a graph with negative weights?

• See . What does it mean for an ant to traverse a negative edge from [math] u \to v [/math] with weight [math] -2 [/math]? Does it shift back all other ants that go through [math] v [/math] by [math] 2 [/math] units?

• Answer:

  Dijkstra's algorithm doesn't work correctly on graphs with negative edges. Therefore, it is perfectly OK that the metaphor with ants doesn't work for such graphs. In Dijkstra's algorithm, you process vertices in the order that corresponds to their minimal distances from the source. During the execution of the algorithm, there are moments when you declare the distance to some vertex to be final -- even though you haven't seen some of the edges in the graph yet. The reason why you can be sure that the distance is final is the assumption that the lengths of the unseen edges are non-negative. Suppose that you run Dijkstra's algorithm from vertex A. It will proceed in the following order: The final distance to A is 0. The final distance to B is 1. The final distance to C is 2. The final distance to D is 9. Oops, we just improved the shortest path to B to 0, even though B has already been processed. Fail. If you have a graph with negative edges but no negative cycles, you can still use a different algorithm (e.g., Bellman-Ford) to compute the lengths of single-source shortest paths. In graphs with negative cycles, it is possible that for some pairs of vertices there is no shortest walk (because you can always walk around the negative cycle more times), and finding the shortest path (i.e., one without repeated vertices) becomes NP-hard.