### sidor's blog

By sidor, 10 years ago,

If I want to find shortest path between A and B with negative edges, but no negative cycle.

How about we start Dijkstra with source A and then with source B and return the minimum of the two results.

I was thinking and I cannot find a counter-example.

Any ideas?

• -8

 » 10 years ago, # | ← Rev. 3 →   +1 counter-example:1 2 51 3 22 3 -73 4 -53 5 14 5 2Path from 1 to 5.
•  » » 10 years ago, # ^ |   0 3-4-5 <= negative cycle
•  » » » 10 years ago, # ^ |   0 There is no 5-3 edge, edges are oriented. If not — so any negative edge is a cycle itselves.
•  » » » 10 years ago, # ^ |   0 Yes, I made a mistake. The weight of edge 3 4 should be -3.
•  » » 10 years ago, # ^ |   0 OK, agreed :) Thanks!
 » 10 years ago, # | ← Rev. 2 →   0 Of course, your idea is wrong: A-C: 100 A-D: 120 C-D: -30 B-C: 100 B-E: 120 C-E: -30 Path from A to B. (ans is 190 in both cases)
 » 10 years ago, # | ← Rev. 2 →   0 Search "dijkstra with potentials" or "ford-bellman".
•  » » 10 years ago, # ^ |   0 But only if you are going to use Dijkstra's algorithm for finding min cost max flow.
•  » » » 10 years ago, # ^ |   0 In general, it doesn't work?
•  » » » » 10 years ago, # ^ |   0 I can't think of any other use for it. To use Dijkstra with potentials, you need to use Ford-Bellman beforehand, to set initial potentials. To find shortest paths just once, you can just use Ford-Bellman. Potentials are needed to run Dijkstra (instead of Ford-Bellman) repetitively on changing graph.
•  » » » » » 10 years ago, # ^ |   0 Understood. Thanks!