I just thought about something.

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?

counter-example:

1 2 5

1 3 2

2 3 -7

3 4 -5

3 5 1

4 5 2

Path from 1 to 5.

3-4-5 <= negative cycle

There is no 5-3 edge, edges are oriented. If not — so any negative edge is a cycle itselves.

Yes, I made a mistake. The weight of edge 3 4 should be -3.

OK, agreed :) Thanks!

Of course, your idea is wrong:

Path from A to B. (ans is 190 in both cases)

Search "dijkstra with potentials" or "ford-bellman".

But only if you are going to use Dijkstra's algorithm for finding min cost max flow.

In general, it doesn't work?

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.

Understood. Thanks!