Блог пользователя sidor

Dijkstra with negative edges.
Автор sidor, 12 лет назад, По-английски

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?

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
12 лет назад, # |
← 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)

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In general, it doesn't work?

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 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.

        → Ответить