-5

does anyone know the algorithm for finding k-shortest path, I searched on Internet and found Yen's but it's so complex ?

Thanks so much.

NoCountry4OldMan
  • 33
  • 5
  • Thanks, just think this website is just for people who knew everything.If we knew, we never go here – NoCountry4OldMan Jan 21 '13 at 08:40
  • 2
    @DzokerP I understand your frustration, but this isn't a site for people who know everything. It is however a site answered by people for free in our free time. If you don't put a lot of effort into a question, others won't spend time on an answer. Try reading Jon Skeet's guidelines on asking a good question: http://msmvps.com/blogs/jon_skeet/archive/2010/08/29/writing-the-perfect-question.aspx – HaemEternal Jan 21 '13 at 08:58
  • 1
    Also I don't think that it is our duty to show him how the algorithm works. Algorithms are full of mathematics, if he/she is not able to understand he/she should learn mathematic. Imho this question has nothing to do with SO and should be placed in mathematica. Furthermore "I find that yen' s algorithm is so long" and "it's so complex" are not showing any effort in understanding the algorithm but showing that he's/she's simply not willing to do the job. -1 – jAC Jan 21 '13 at 09:07
  • at least there is a human here... – NoCountry4OldMan Jan 21 '13 at 09:30
  • 2
    There is a very good answer explaining the algorithm here: http://stackoverflow.com/questions/12870122/eppsteins-algorithm-and-yens-algorithm-for-k-shortest-paths – 79E09796 Jan 21 '13 at 16:46

3 Answers3

3

It cannot be done efficiently (polynomially)1 - the problem is NP-Hard

Think of it this way - is you could find even the length of a k shortest path (asssume simple path here) polynomially, by doing a binary search on the range [1,n!] for k, you could find if there is a hamiltonian path in the graph (by finding a path of length n).

Since the hamiltonian path problem is NP-Hard, so does this problem, and there is no known polynomial solution to it.

(1)probably, unless P=NP, but most CS researchers believe it is very unlikely

amit
  • 175,853
  • 27
  • 231
  • 333
1

Altogether now...

Google for Djikstra's Algorithm. There's an implementation here.

Matt
  • 1,648
  • 12
  • 22
0

This is solved with dis-joint set. Google it but in short you have 2 vectors. one for parents initialized with -1. the other for rank initialized with zero's. Now start at the source node. you go for each possible node you can get from there. add them to your set by making their parent[i] = current node. the decision which one will be the parent of who is done based on the rank[i] which holds the number

blackmath
  • 242
  • 1
  • 10