sidor's blog

Dijkstra with negative edges.
By sidor, 12 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

»
12 years ago, # |
← 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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3-4-5 <= negative cycle

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

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

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

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

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

    OK, agreed :) Thanks!

    → Reply
»
12 years ago, # |
← 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
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      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
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In general, it doesn't work?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          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