Представление кратчайших путей в алгоритме

Пусть G=(V,E) - заданный граф. Для каждой вершины vÎV мы будем помнить ее предшественника p[v] . Предшественник – это либо другая вершина, либо NIL.

По завершении работы алгоритма цепочка предшественников, начинающаяся с произвольной вершины v, будет представлять кратчайший путь из s в v.

 

Ориентированный подграф предшествования G_p=(V_p,E_p), определенный так:

V_p ={ vÎV :p [v] ≠ NIL }È { s },

E_p={(p [v], v) Î E: vÎ V_p \{ s }},

по окончании работы алгоритмов будет «деревом кратчайших путей».

 

Пример графа

 

 

 

 

Граф предшествования (вариант 1)

 

 

 

Граф предшествования (вариант 2)