How to understand "predecessor node" of the winning paths?
4 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
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]?
0 Kommentare
Akzeptierte Antwort
Lucio Cetto
am 6 Mai 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 Kommentar
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!