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

Автор SmartCoder, 15 лет назад, По-английски

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
  • Проголосовать: не нравится

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

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