Thread Subject: Graph theory, allshortestpaths, show parts of the path

Hello, can somebody help me please?

I found a matlab built-in function allshortestpaths which is usefull for my needs but Iam looking for some expansion of this function. Result of this function is matrix with final values of all shortest paths between all nodes. What I need is next matrix or something similar where will be values of steps which are parts of final value in better case sequence of nodes from start to destination. For example: Value of shortest path between nodes 1 and 6 is 5 and I need to show result where will be shown, that value 5 is sum of 1, 2, 2(edges weights) or the path from 1 to 6 is sequence of nodes 1, 3, 5 and the same for all others result (1 to 5, 2 to 5 ...). Is this possible without use Dijkstra's algorithm for every path separately? Thank you for your help a excuse me for my bad English.

Hello Adam:
If you have the Bioinformatics Toolbox you can use the first and third output of graphshortestpath, this function is -vectorized- which means that you do not have to repeat for every possible path, you only need to do it for every node. Recall that all shortest distances to a single node can well be represented by a tree of predecessors.
HTH
Lucio

"Adam " <adamrimsky@seznam.cz> wrote in message <hcuodf$liq$1@fred.mathworks.com>...
> Hello, can somebody help me please?
>
> I found a matlab built-in function allshortestpaths which is usefull for my needs but Iam looking for some expansion of this function. Result of this function is matrix with final values of all shortest paths between all nodes. What I need is next matrix or something similar where will be values of steps which are parts of final value in better case sequence of nodes from start to destination. For example: Value of shortest path between nodes 1 and 6 is 5 and I need to show result where will be shown, that value 5 is sum of 1, 2, 2(edges weights) or the path from 1 to 6 is sequence of nodes 1, 3, 5 and the same for all others result (1 to 5, 2 to 5 ...). Is this possible without use Dijkstra's algorithm for every path separately? Thank you for your help a excuse me for my bad English.

Hello Lucio, thank you for your answer but can you explaine me in more details how can i use these outputs? I read matlab help for this function but I dont know how to use this function to solve my problem. In matlab help they are finding shortest path only from node 1 to 6 but I dont know how to set parameters to find shortest paths (vector path) between every nodes without applying this function on every possible path (without setting every source and destination). Simply I dont know how to use that first and third output of graphshortestpath function to get the sequence of nodes, between all nodes, for every shortest paths. Iam sorry for these noob questions but iam newcomer in matlab and i need every help.

Hello Lucio,
Iam sorry that Iam repalying again but yesterday I was too tired to thing clearly (it was 9PM when I wrote last message). So I have found matlab function graphpred2path which returns vector path from vector pred. But Iam not sure how to use this function to solve my problem. I must call function graphshortestpath for every node but with which parameters (source and dest. will be 1,6;2,6;3,6 ... or different)? And when I get all pred vectors how tu use them with graphpred2path function (param. will be matrix of pred vectors and matrix of destinations or different)? Or this is not usefull and process must be different? Again, thank you very much for your potential help.

Adam:
You almost have the solution, you'll need to iterate for every node, but not for every path, and it is also important that you understand that the all shortest patch to (or from) one node to all others can be represented with a tree... for example in

 W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21];
 DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)
[dist,path,pred] = graphshortestpath(DG,1)
dist =
         0 1.3600 0.5300 0.5700 0.2100 0.9500
path =
    [1] [1x5 double] [1x3 double] [1x3 double] [1x2 double] [1x4 double]
pred =
     0 6 5 5 1 4

you get all shortest paths from node 1 to all other nodes
if you want the path form node 1 to node 3 you can do:
[pred(pred(3)) pred(3) 3]
ans =
     1 5 3

or you could have done also path{3}

But the important thing is that now you can use the retuned indices to index into the dist vector, so you'll find the cumulative edge length that you were asking for:
dist(path{3})
ans =
         0 0.2100 0.5300

In short, you can get all the cumulative paths from Node 1 with:

allfrom1 = cellfun(@(x) dist(x),path,'Uniform',false)

for example from 1 to 6 would be:
allfrom1{6}
ans =
         0 0.2100 0.5700 0.9500

You just now need to iterate for every node.


Lucio

Adam Ř?msk? <adamrimsky@seznam.cz> wrote in message <1731825812.19645.1257501556341.JavaMail.root@gallium.mathforum.org>...
> Hello Lucio,
> Iam sorry that Iam repalying again but yesterday I was too tired to thing clearly (it was 9PM when I wrote last message). So I have found matlab function graphpred2path which returns vector path from vector pred. But Iam not sure how to use this function to solve my problem. I must call function graphshortestpath for every node but with which parameters (source and dest. will be 1,6;2,6;3,6 ... or different)? And when I get all pred vectors how tu use them with graphpred2path function (param. will be matrix of pred vectors and matrix of destinations or different)? Or this is not usefull and process must be different? Again, thank you very much for your potential help.

Thank you very much Lucio for your help. I was last week out so I can replay till today. Your answer is very usefull but could you help me in one last thing? In your last answer you wrote that iam asking for cumulative edge length but, perhaps I dont understand to your answer enough, I need to know all shortest paths from source node, for example 1 to all other nodes from node 2 to all other ... which will be showed in sequenc of nodes between them. As you wrote:

you get all shortest paths from node 1 to all other nodes
if you want the path form node 1 to node 3 you can do:
[pred(pred(3)) pred(3) 3]
ans =
1 5 3

and these results is what I need. This sequenc for all paths (1 to 2,3,4; 2to 1,2,3;...). Is there any possibility how to iterate this procedure for all nodes? Once more thank you very much for any help