sidor's blog

By sidor, 10 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?

Read more »

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