How to understand "predecessor node" of the winning paths?

2 views (last 30 days)
the function graphshortestpath in Matlab is called as
[DIST,PATH,PRED] = GRAPHSHORTESTPATH(G,S)
For the first example in the webpage, in digraph from node 1 to node 6, the dist=0.95, path=[1 5 4 6], this is easy for us to understand. While the pred=[0 6 5 5 1 4], the first element (0) in pred is understandable, but how to interpret 6, 5, 5, 1 and 4?
According the defintion of pred in Matlab user help "pred contains the predecessor nodes of the winning paths" and definition of “predecessor node” in theory>, the predecessor node of one node is those nodes that preceeding the node, so the predecessor nodes of path [1 5 4 6] shall be [0 6 5(for 1), 3 4(for 5) ,6 1(for 4), 2 3(for 6)], why the return results by Matlab is [0 6 5 5 1 4]?

Accepted Answer

Lucio Cetto
Lucio Cetto on 6 May 2011
The PRED in your example 'encodes' all shortest paths from S to all other nodes, for example the shortest path between 1 and 6 is PRED(6) = 4, PRED(4) = 5, PRED(5) = 1 and PRED(1) = 0, therefore the path is (in reverser order) 1-5-4-6. But with the same output you could figure out the minimum path between 1 and 3: i.e. PRED(3) = 5, PRED(5) = 1 and PRED(1) = 0, giving the path 1-5-3.
  1 Comment
Moritz H
Moritz H on 4 Aug 2016
Edited: Moritz H on 4 Aug 2016
Oh, now that I think about it, it makes sense. :D PRED(6) ans=4 and you get the next node by doing PRED(ans).
Thank you!

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by