Построение деревьев кратчайших путей.

В общем случае строятся p деревьев кратчайших путей. Нам нужно построить 5 деревьев.

Построим эти деревья, зная длины кратчайших путей (они стоят в матрице D ₅) и ориентируясь по диаграмме на рис. 9.

Деревья показаны на рис. 10.

Замечание. Если в графе отсутствуют контуры отрицательной длины, то в каждой строке и каждом столбце матрицы D_p по крайней мере одна длина сохраняется такой же, какой она была в матрице D ₀ (длина кратчайшего пути из одной дуги). В нашем случае имеем:

Эти числа показаны в матрице жирным шрифтом и подчеркнуты. Только из соответствующих дуг и могут состоять деревья кратчайших путей, каждый подпуть в которых, в частности, путь из одной дуги, - кратчайший.

Если указанное условие не выполняется, в графе имеются контуры отрицательной длины, и задача о кратчайшем пути не имеет решений.

,