Построение деревьев кратчайших путейВ общем случае строятся p деревьев кратчайших путей. Нам нужно построить 5 деревьев. Построим эти деревья, зная длины кратчайших путей (они стоят в матрице D 5) и ориентируясь по диаграмме на рис. 9. Деревья показаны на рис. 10.
Замечание. Если в графе отсутствуют контуры отрицательной длины, то в каждой строке и каждом столбце матрицы Dp по крайней мере одна длина сохраняется такой же, какой она была в матрице D 0 (длина кратчайшего пути из одной дуги). В нашем случае имеем:
Эти числа показаны в матрице Если указанное условие не выполняется, в графе имеются контуры отрицательной длины, и задача о кратчайшем пути не имеет решений.
|
жирным шрифтом и подчеркнуты. Только из соответствующих дуг и могут состоять деревья кратчайших путей, каждый подпуть в которых, в частности, путь из одной дуги, - кратчайший.
