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

2 views (last 30 days)
s on 1 Mar 2011
Edited: Moritz H on 4 Aug 2016
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]?

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.
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!