OJ Board

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

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

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

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?

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.

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.

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

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

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.

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.

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

Thanks!