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

Shortest Paths problem setter "Petr" :)
Автор Killever, 13 лет назад, По-английски

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

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

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

The article "Finding the k Shortest Paths" by David Eppstein might help you.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Твой пост в русском языке, топикстартер его не видит.
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    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.

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

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

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 :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The article "Finding the k Shortest Paths" by David Eppstein might help you.
→ Ответить