How can i get all paths between two nodes ??

How can i get all paths between two nodes

[Geoff Hayes]

Shaifali - you will need to provide some more details. Do you have a matrix representing all paths between a set of nodes and you wish to find all paths between just two of them?

[shaifali shakya]

yes i have a matrix representing all paths between a set of nodes and i wish to find all paths between source and destination.

Answer 1

[Kelly Kearney]

If you're looking for the shortest paths, there are a few FEX entries that implement algorithms for this, including both depth-first and breadth-first searches. I use matlab_bgl, which includes several shortest path algorithms.

However, if you're really looking for all paths between two nodes, I found that algorithms for that are more scarce. I wrote pathbetweennodes.m to do just that... I wrote it for fairly small graphs (~50 nodes or fewer), so I'm not sure how efficient it might be for larger graphs, but it has worked well for my purposes.

[Kelly Kearney]

An update on my answer, since this is now out of date...

I've moved this function to GitHub: https://github.com/kakearney/pathbetweennodes-pkg.

Also, Matlab 2015b and above now includes some native shortest path methods for graph objects, so you don't need matlab_bgl.

[Pham Minh Cong]

Great work !

Thank you for your contribution.

I am new to this subject, do you have a name for your algorithms ?

Answer 2

[Emad NB]

You can use my function below. I use weight factor as a signal to find different pathes:

function pth=pathof(graph,startn,endn)
stop=0;
n=0;
while stop~=1
    n=n+1;
    Temp=shortestpath(graph,startn,endn);
    eidx=findedge(graph,Temp(1:end-1),Temp(2:end));
    if n~=1
        if length(Temp)==length(pth{n-1,1})
            if Temp==pth{n-1,1}
                stop=1;
            else
                pth{n,1}=Temp;
                graph.Edges.Weight(eidx)=100;
            end
        else
            pth{n,1}=Temp;
            graph.Edges.Weight(eidx)=100;
        end
    else
        pth{n,1}=Temp;
        graph.Edges.Weight(eidx)=100;
    end
    clear Temp eidx;
end

[mujahid razman]

Simulate any shortest path algorithm between point A to point B if the map is known. Consider the map consists of free space and any configuration of finite obstacles. The result can be shown in 2-D graph where 0 means obstacle, 1 means free space and 2 means trajectory followed. For instance you can simulate A* algorithm in Matlab.

how to solve please help

[Image Analyst]

Why not use bwdistgeodesic()? Your problem statement is exactly what Steve worked on. Did you overlook my answer with the link to his blog?

The above image is from part 5 of his blog series. Don't you think that pretty much describes your problem?

Answer 3

[Image Analyst]

See Steve's blog series on this: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/