Multiple Shortest Pathways--Help in understanding Yen's k shortest path algorithm

[hanniballector]

Hello Everyone,
I have been for the last couple of days,well two weeks to be precise, been trying to implement Yen's k shortest path algorithm. The algorithm is described in a paper from the 1970s

The link K-th Shortest Path Problem has the paper and a few previous papers in case someone is interested in learning more about the algorithm and its alternatives.

Basically, Yen's algorithm is a mutation algorithm which gets rids of segments(called arcs in the paper) of the previously shortest paths and recomputes the shortest path. I have been using dijkstra's algorithm in order to get the shortest paths.(it works just fine, I ran multiple tests on it.)

So, I have been trying to get Yen's algorithm working, and I have run into a theoretical question. Let us assume that we have a random graph in which the first 6 paths between nodes 0 and 50 are as follows: (Generated via a BFS algorithm to get all the paths connecting the two nodes which are then sorted)

0 375 45 46 47 49 50 1.160189
0 375 45 47 49 50 1.16443
0 375 45 46 47 48 50 1.164553
0 375 45 47 48 50 1.168793
0 375 45 46 47 48 49 50 1.174494
0 375 45 47 48 49 50 1.178735

here the floating point number at the end of each line is the "distance" of the path. My question is, how does the Yen's algorithm get the 6th path. From my understanding of the paper it checks if the the first i nodes of the k-1th path correspond to the first i nodes of the previously found paths, if so then d[i][q]=infinity where q is the next node in the path.
Practically speaking to get from the 1st path to the 2nd path, we remove 45-46 in the first path and it recomputes the path. To get from 2nd to 3rd, we get rid of 47-49 in the second path forcing the algorithm to find a new path linking 0 through 47 and 47 through 50 which can then stored.
But when we get to the 6th path, it removes 45-46 but it has to also remove 45-47 since the first 3 nodes of the 5th path also matches the first 3 nodes of the 2nd path( if we don't set this to infinity, then the alogrithm starts cycling between shortest found paths). I do not see how we can get the 6th shortest path.
Any ideas? Am I missing something completely obvious from the paper? Can anyone recommend any books/articles that I can go through which might better explain this. I would prefer not to look through other people's implementation(I have found some MATLAB implementation online but I have been having problems getting through the syntax--it also doesn't help that the documentation for the code is in mandarin). In case someone coded up a solution in C which has some documentation in english that would be helpful too.
Message me in case you guys need more information, and Thanks for all the help.
-H

[quzah]

Segment1 = 0,375,45

All paths now look like:
Segment1,(rest of path)

Sgement2 = 46,47
Now you have two paths that look like:
Segment1,Segment2,(rest of path)

Segment3 = 47,48
Now you have two paths that look like:
Segment1,Segment3,(rest of path)

Segment4 could be 49,50
Which would make path 6 be:
Segment1,Segment3,Segment4


Right?


Quzah.

[hanniballector]

I don't think that is the right way. Because when you get rid of 47-48(with the current path being 0 375 45 46 47 ? ? ? 50) you also have to get rid of 47-49(from the first path because they match up to 47). This is done because other wise the routine will start cycling between the 5 paths by identifying the next shortest path as a the first path found.
I tried a gimmick where the path was only accepted if it was greater in lenght than the previously found shortest path. However, this could lead to more problems because will a new path will be found, it is not going to be the shortest one.
Any software engineers trawling these fourms. Any help would be very much appreciated. Thanks!
-H
ps When you remove any arc (say 46-47), the new path is found between 46 and 50 which is then concatinated to the previous found 0 375 45 46. The argument being that the kth path matches up with a previously found path up to the ith node and it then diverges.

Segment1 = 0,375,45

All paths now look like:
Segment1,(rest of path)

Sgement2 = 46,47
Now you have two paths that look like:
Segment1,Segment2,(rest of path)

Segment3 = 47,48
Now you have two paths that look like:
Segment1,Segment3,(rest of path)

Segment4 could be 49,50
Which would make path 6 be:
Segment1,Segment3,Segment4


Right?


Quzah.

[quzah]

I don't understand your link's explanation of the problem. From what I gather, you are trying to find the cheapest cost in the cheapest number of moves. I don't know why you need this algorithm at all. You've already done a BFS and come up with X paths that all take the same number of moves. So simply find out which one summed up to the cheapest travel (which you have already done), and use that. This algorithm serves no purpose.


Quzah.

[phantomotap]

I'm not getting it either...

Soma

[hanniballector]

sorry for the late reply. I have work most days late in the evening so I was not able to check this up to now.
Here is a second resource
Yen (1971) Finding the K Shortest Loopless Paths in a Network (Management Sci) - Integrable Differential
Both the original paper and a pseduo code implementation are presented. Can you please take a look and help me understand why this algorithm works.
The reason why I do not want to implement a bfs is because of the complexity involved. BFS takes far longer to find all the possible paths and if I want only the top 10 there is an additional component of sorting it which takes up more computing time. I need a very fast implementation of k shortest paths and Yen's algorithm seemed very promising.

I'm not getting it either...

Soma

[quzah]

BFS is used to find the shortest path, not every possible path. A flood fill is basically the opposite of what you're trying to achieve:

##########
#01234567#
#1#3#5##8#
#234#67#9#
#3####8###
#4##BA9A##
#5##C##BC#
#6##B#DCD#
#789AB##E#
##########

Every A took the same number of moves to get there. Every 4 took the same number of moves to reach it. That's what a BFS (flood fill) does.

What you really have to decide is what you want to measure. Do you want to measure the shortest number of moves, or the cheapest cost in terms of weight?

See that algorithm in your first link didn't make sense to me because they had plenty of paths that were 0 cost, but instead they took ones that were 10 in cost, because it was less moves.

You confused the issue by starting off with "I have a bunch of paths generated by BFS..." You need to really decide what it is you want, and why you want it. If this is homework for the sake of being homework, ok, have fun. But if you're really trying to find the shortest path(s), you would do well to ask yourself why you think you need multiple shortest paths, and how many times you think you'll need to compute all of them.

The link you provided talks about computing every possible path, and then sorting them by length/cost. That's different than what your first post seemed to want.


Quzah.

[AAAMR]

Hi,

I think BFS works well for finding single shortest path (SP) and the similar principle is used by Dijkstra's algorithm as well [refer to introduction to algorithm]. On the other hand, for multiple SPs, one needs to find all possible paths first (if using BFS) and then sort according to their cost. This approach has a high computational complexity and is similar to exhaustive search. In such cases, Yen's algorithm (Finding the K shortest Loopless path in a network, 1971 - 713 citations) has one of the best upper bound computational complexity [refer to Finding the K shortest simple paths: A new algorithm and its implemntation (2007, 102 citations)" - page:2, 1st paragraph].

I am trying to do a similar thing atm and facing the same problem. I looked at the 2nd link and had to make some changes to get it to work. hanniballector, any solutions yet?

I will share mine if I crack it.

btw, does the matlab code work, i.e.; solve the problem? link please...

-AR