Shortest path

cet · Post by **cet** » Sun May 21, 2006 2:29 am

How to find m-th shortest path in weighted graph.

ilyaraz · Post by **ilyaraz** » Wed May 31, 2006 3:02 am

IMHO, it looks some kind of DP. But I'm not actually sure.

Cosmin.ro · Post by **Cosmin.ro** » Wed May 31, 2006 12:26 pm

It's pretty complex, you could search for k shortest path on google or look over this paper: http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html

Krzysztof Duleba · Post by **Krzysztof Duleba** » Wed May 31, 2006 2:22 pm

Complex? Paper? You can have a O(km log kn) solution simply by modifying Dijkstra algorithm a little bit. Are you talking about something more efficient?

Cosmin.ro · Post by **Cosmin.ro** » Thu Jun 01, 2006 12:34 am

Can you? I alwayes thought it is a hard problem, I never looked into it really hard. Could you give some detailes to the Dijkstra sol? I would be very interessted.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jun 01, 2006 12:51 am

In SSSP you extract each node from a queue exactly once. Instead extract it exactly k times. Keep inserting it until then. I solved problem 10740 this way.

Can you explain the idea of DP solution in a few words?

Edit: never mind, I read some papers on that. I admit that I seriously underestimeted the problem, some pretty complex O(k * m) solutions exist. However, in most cases you don't need to tune it so much.

Cosmin.ro · Post by **Cosmin.ro** » Thu Jun 01, 2006 1:27 am

I wonder if this sol runs in time on sgu: http://acm.sgu.ru/problem.php?contest=0&problem=145

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jun 01, 2006 2:17 am

No, it's very memory consuming, no way to fit into 1 MB. I'll try to solve this problem tomorrow.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jun 01, 2006 9:20 pm

But this is a completely different problem. UVA's 10740 is about any k-th path, SGU's 145 is about k-th *simple* path. I was able to optimize my algorithm to use only O(k * n + m) memory replacing std::priority_queue by std::set, but now I can't see how it can be applied.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jun 01, 2006 10:14 pm

After a few adjustments and paying a price of O(n) time factor (now it's O(kmn)) I got MLE on test 6. I'm not sure if this approach can be improved any further in case of simple paths.

Edit: It can be improved, but only to MLE on test 12 so far.

Gaizka · Post by **Gaizka** » Mon Sep 18, 2006 5:58 am

Can you explain the modification to the dijkstra algorithm a little better? Im sorry, but I just don't get it!

Thanks!