Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Graph theory, allshortestpaths, show parts of the path
Date: Fri, 6 Nov 2009 16:24:33 +0000 (UTC)
Organization: The MathWorks Inc
Lines: 43
Message-ID: <hd1ik1$r2n$1@fred.mathworks.com>
References: <hcuurn$fj3$1@fred.mathworks.com> <1731825812.19645.1257501556341.JavaMail.root@gallium.mathforum.org>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1257524673 27735 172.30.248.35 (6 Nov 2009 16:24:33 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 6 Nov 2009 16:24:33 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 222043
Xref: news.mathworks.com comp.soft-sys.matlab:583051


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 &#344;?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.