K'th Shortest Path

[sunny]

http://acmicpc-live-archive.uva.es/nuev ... php?p=3624

If there wasn't the constraint that a vertex can't be visited multiple times, an easy O (k*E*log(k*V)) solution was possible.

But how to do this?

[sclo]

use a modified form of dijkstra.
For each node, we are allowed to remove it at most k times from the heap, instead of only once. And each time we remove it from the heap, we update distances of neighbors and insert them into heap.

[forest]

i suppose it is the same algorithm sunny was talking about. It allows vertexes appear multiple times

[ImLazy]

I heard that the generalizations of Dijkstra can not handle loopless paths.

[sunny]

I didn't understand how sclo's algorithm can find cycle-less paths.
Otherwise, I too think it is the same thing I mentioned for finding cycle-allowed K'th shortest path.

Well I tried to modify that algorithm. I store one additional information for every node which is the intermediate vertices visited to get to that node. This is to not allow any cycles.

As every vertex is proccessed upto K times so the number of nodes can be K*V. So, overall runtime becomes K^2*E*log(KV) which gets TLE.

[ImLazy]

The offical report of Yokohama 2006 gives the algorithm.

[richardxx]

I heard that the generalizations of Dijkstra can not handle loopless paths.

But, indeed it solves the loopless form.
Try add the information into the dijkstra label, any time we expand the label according to this visiting information. This can be done with bits operations.

Say:

0110011

We have visited the 1st,2nd,5th and 6th city, so if these cities can be reach from this point, we simply ignore them.