Killever's blog

Shortest Paths problem setter "Petr" :)
By Killever, 13 years ago, In English

problem link
http://acm.sgu.ru/problem.php?contest=0&problem=314
how i can deal with cases like case 3.
my solution is backtracking to get all paths form start to end
and sort them by cost .

any hint ?
thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My first idea is O(K*NlogN). You can solve this problem by running K times Dijkstra's algorithm.

I explain: you have to modify Dijkstra in a way that it never finds a path from S to D of length equal to "L".
Dijkstra(S, D, L) // finds path from S to D not equal to L

It's easy to implement: when you relax distances, you firstly check if the node you're relaxing is D and the distance found is equal to L, if it is, you don't relax! (If "X" is the absolutely minimal distance, you will necessarily find a path greater than X, if it exists).

Then do this way:

Min_dist = Integer.MAX_VALUE
For i=1 to K
....Min_dist = Dijkstra(S, D, Min_dist);

When i=1 the call to Dijkstra returns the absolute minimal distance (it never finds a path of length "Integer.MAX_VALUE"). Next times, it must find only lengths greater than "Min_dist".
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You mean O(K*MlogN)? This is about 10^10 :)

    I solved this problem several years ago, my solution was according to the Eppstein's article. And I viewed other solutions - they were in fact the same too.

    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This doesn't seem right for a number of reasons :)

    1) There can be a lot of different paths with the same length. You should consider all of them.
    2) The complexity of your algorithm is probably too high
    3) The algorithm itself is not correct: imagine a graph like this (all edges have a unit length):
        1->2<->3
    Suppose you want to find 2nd path from 1 to 2. It should be 1->2->3->2. However, if you don't relax node 2, you won't be able to find it.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1) I understood this way: if there are paths of length 2, 2, 3, 4, 5, 5 ... you have to write out these: 2, 3, 4, 5 ...
      2) Might be :)
      3) Right... I haven't thought about that because I used this algorithm in a problem like this (but with K=2) with a DAG (if I'm not mistaken)
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Btw, when Petr commented this problem from his problemset, he said that he gave this problem just to show that such a beautifully powerful algorithm exists :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    This particular algorithm is neither beautiful nor powerful, IMHO. :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes, possibly, the result itself is more interesting than the algorithm
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The article "Finding the k Shortest Paths" by David Eppstein might help you.
→ Reply