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

the function graphshortestpath in Matlab is called as

[DIST,PATH,PRED] = GRAPHSHORTESTPATH(G,S)

(see http://www.mathworks.com/help/toolbox/bioinfo/ref/graphshortestpath.html),

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]?

Answer 1

[Lucio Cetto]

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]

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!