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

3 visualizaciones (últimos 30 días)
s
s el 1 de Mzo. de 2011
Editada: Moritz H el 4 de Ag. de 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]?

Respuesta aceptada

Lucio Cetto
Lucio Cetto el 6 de Mayo de 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 comentario
Moritz H
Moritz H el 4 de Ag. de 2016
Editada: Moritz H el 4 de Ag. de 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!

Iniciar sesión para comentar.

Más respuestas (0)

Categorías

Más información sobre Graph and Network Algorithms en Help Center y File Exchange.

Community Treasure Hunt

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

Start Hunting!

Translated by