sidor's blog

Dijkstra with negative edges.
By sidor, 14 years ago, In English

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?

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
14 years ago, hide # |
← Rev. 3  
Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
14 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
14 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      In general, it doesn't work?

      → Reply
      • »
        »
        »
        »
        14 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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.

        → Reply