Thread Subject:

Finidin the nodes of the shortest path

Hi all,

I am trying to find all possible shortest paths ( the path itself not the distance) for a undirected graph for which all weights are equal. The function
 "graphshortestpath" gives only one possible shortest path between any two nodes while there may be many. How can I find the rest??
 
For my data, I have 64-node undirected graph for which the shortest path between nodes 1 and 3:

[dist,path,pred] = graphshortestpath(UG,1,3,'directed',false);
 path
path = 1 7 55 3

and funny enough if you try to exchange the nodes you get another possible root for the shortest path betwen nodes 1 and 3.

[dist,path,pred] = graphshortestpath(UG,3,1,'directed',false);
path
path = 3 13 61 1


I'll come back with a whole code if needed.
Any ideas please?
Many thanks
 

"Jack " <jack_sama_1981@yahoo.com> wrote in message
news:hvo5ac$k8r$1@fred.mathworks.com...
> Hi all,
>
> I am trying to find all possible shortest paths ( the path itself not the
> distance) for a undirected graph for which all weights are equal. The
> function "graphshortestpath" gives only one possible shortest path between
> any two nodes while there may be many. How can I find the rest??

I'm assuming this is a graph not a multigraph.

http://en.wikipedia.org/wiki/Multigraph

Let's call the two vertices A and B (assuming A ~= B) and the length of the
shortest path between them n.

If A and B are adjacent, then there is only one shortest path between
them -- the edge they share -- and n is 1.
If A and B are not adjacent, then for each vertex C adjacent to A find all
shortest paths from C to B (using recursion) and add on the edge from A to C
to each of those paths. Discard any such paths of length > n.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

"Steven Lord" <slord@mathworks.com> wrote in message <hvqtvk$1jp$1@fred.mathworks.com>...
>
> "Jack " <jack_sama_1981@yahoo.com> wrote in message
> news:hvo5ac$k8r$1@fred.mathworks.com...
> > Hi all,
> >
> > I am trying to find all possible shortest paths ( the path itself not the
> > distance) for a undirected graph for which all weights are equal. The
> > function "graphshortestpath" gives only one possible shortest path between
> > any two nodes while there may be many. How can I find the rest??
>
> I'm assuming this is a graph not a multigraph.
>
> http://en.wikipedia.org/wiki/Multigraph
>
> Let's call the two vertices A and B (assuming A ~= B) and the length of the
> shortest path between them n.
>
> If A and B are adjacent, then there is only one shortest path between
> them -- the edge they share -- and n is 1.
> If A and B are not adjacent, then for each vertex C adjacent to A find all
> shortest paths from C to B (using recursion) and add on the edge from A to C
> to each of those paths. Discard any such paths of length > n.
>
> --
> Steve Lord
> slord@mathworks.com
> comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com
>

Dear Steve;

Thanks for your contribution.

You are right; this is a a graph not a multigraph.
You wrote:
"... If A and B are not adjacent, then for each vertex C adjacent to A find all
shortest paths from C to B (using recursion)..."
but the problem here is to find all shortest paths from C to B; if I were able to do this then I would've done it between A and B!!! unless I misunderstood what you meant.

So for the following simple example:
I have undirected graph with 5 nodes and 5 edges and I want to find the shortest path between node# 1 and node# 3.

W = .5*[1 1 1 1 1 1 1 1 1 1 ];
DG = sparse([1 1 2 2 3 3 3 4 4 5 ],[2 4 1 3 5 4 2 1 3 3],W);
UG = tril(DG + DG');
[dist,path,pred] = graphshortestpath(UG,1,3,'directed',false);
path = 1 2 3
While there is another path = 1 4 3 which is not given by matlab.

I hope that explaines what I wanted.

Many thanks

"Jack " <jack_sama_1981@yahoo.com> wrote in message
news:hvu99k$j83$1@fred.mathworks.com...
> "Steven Lord" <slord@mathworks.com> wrote in message
> <hvqtvk$1jp$1@fred.mathworks.com>...
>>
>> "Jack " <jack_sama_1981@yahoo.com> wrote in message
>> news:hvo5ac$k8r$1@fred.mathworks.com...

*snip*

> Dear Steve;
>
> Thanks for your contribution.
>
> You are right; this is a a graph not a multigraph.
> You wrote: "... If A and B are not adjacent, then for each vertex C
> adjacent to A find all shortest paths from C to B (using recursion)..."
> but the problem here is to find all shortest paths from C to B; if I were
> able to do this then I would've done it between A and B!!! unless I
> misunderstood what you meant.

Consider the graph with A removed (since we don't want to consider "shortest
paths" from C to B that backtrack through A.)
What happens if you *_recursively_* apply that procedure to the modified
graph with C also removed to locate the shortest paths from C to B using the
shortest paths from D to B where D is adjacent to C?
What happens if you *_recursively_* apply that procedure to the
twice-modified graph with D also removed to locate the shortest paths from D
to B using the shortest paths from E to B where E is adjacent to D?
What happens if you *_recursively_* apply that procedure ...

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com