Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Finding all possible paths using Yen's Algorithm

Subject: Finding all possible paths using Yen's Algorithm

From: Acute Forever

Date: 13 Dec, 2011 10:11:02

Message: 1 of 4

Hi All

I need to find all possible paths using Yen's algorithm.

When we call implementation of Yen's algorithm as given in:
http://www.mathworks.com/matlabcentral/fileexchange/32513

We need to specify four parameters: netCostMatrix, source,
destination, k_paths

Where k_paths is a number which should be given as input to find k
number of paths.

I need a slight modification in this. If i need to find all the
possible paths between a Source and a Destination what should be done?
In this case i cannot specify the parameter "k_paths" in the beginning
and need to update it until all possible paths are found between a
source and a destination.

Any help in this regard would be of great value.

Best Regards

Subject: Finding all possible paths using Yen's Algorithm

From: ImageAnalyst

Date: 13 Dec, 2011 12:47:36

Message: 2 of 4

Steve Eddins currently is doing a whole series on path finding,
including finding all reasonable paths and ways to whittle it down to
one path.
http://blogs.mathworks.com/steve/2011/12/13/exploring-shortest-paths-part-5/

Not sure if you have a 2D array or image, but ..... Note: all possible
paths for an image or N-Dimensional matrix, instead of a directed
graph/network, would essentially be infinite because you could always
keep scribbling over the image for miles and miles, but as long as you
end at the destination, it's still a path, and there is a virtually
infinite number of ways you could scribble over an image. But there
are several ways to get "shortest" paths (there will be more than one
if you think about it) of the same length.

Subject: Finding all possible paths using Yen's Algorithm

From: NetScience

Date: 13 Dec, 2011 13:25:31

Message: 3 of 4

On Dec 13, 1:47 pm, ImageAnalyst <imageanal...@mailinator.com> wrote:
> Steve Eddins currently is doing a whole series on path finding,
> including finding all reasonable paths and ways to whittle it down to
> one path.http://blogs.mathworks.com/steve/2011/12/13/exploring-shortest-paths-...
>
> Not sure if you have a 2D array or image, but ..... Note: all possible
> paths for an image or N-Dimensional matrix, instead of a directed
> graph/network, would essentially be infinite because you could always
> keep scribbling over the image for miles and miles, but as long as you
> end at the destination, it's still a path, and there is a virtually
> infinite number of ways you could scribble over an image.  But there
> are several ways to get "shortest" paths (there will be more than one
> if you think about it) of the same length.

Hi

Thank you for the reply.

I have an undirected graph and i want to find all possible shortest
paths. The only point is that i am using Yen's K-shortest paths
algorithm but don't want to limit it to "K" number of paths, rather i
need to know all possible shortest paths.

The graph looks like this:

N1 =[1 1 2 2 2 3 3 3 4 5 6];
N2 =[2 4 3 5 6 6 5 7 5 6 7];
W = [10 10 10 10 5 20 15 20 10 20 10];

netCostMatrix(1:length(N1),1:length(N1)) = inf;
        for i = 1 : length(N1)
            netCostMatrix(N1(i),N2(i)) = W(i);
            netCostMatrix(N2(i),N1(i)) = W(i);
        end

When Yen's algorithm is called, we need to specify parameters in
following way:
kShortestPath(netCostMatrix, source, destination, k_paths)

Where netCostMatrix is the graph, source and destination are source
and destination nodes respectively, we have to specify all of them.
The only thing i don't want to fix is the parameter "k_paths", program
should keep on executing until it finds all possible shortest
paths(even if they are 10 in number, i.e k goes upto 10).

Thank you once again for the help.
Best Regards

Subject: Finding all possible paths using Yen's Algorithm

From: Derek O'Connor

Date: 14 Dec, 2011 13:32:08

Message: 4 of 4

NetScience <acute4ever@gmail.com> wrote in message <d260a92e-39c1-4553-
> I have an undirected graph and i want to find all possible shortest
> paths. The only point is that i am using Yen's K-shortest paths
> algorithm but don't want to limit it to "K" number of paths, rather i
> need to know all possible shortest paths.
--- snip ---


Would the Floyd-Warshall All Pairs Shortest Path Algorithm be useful here?

See: http://www.mathworks.co.uk/matlabcentral/answers/16192-inversion-of-a-boolean-matrix

You would need to add some statements to the F-W algorithm to record the paths, but that is not difficult.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us