Результаты вычислений в задаче, решенной с, помощью алгоритма Дейкстры

Как видно из таблицы, узлу t приписывается постоянная пометка = . Следовательно, длина кратчайшей цепи из узла s в узел t равна 7. Эта цепь состоит из дуг, для каж­дой из которых разность между значениями постоянных поме­ток ее концевых узлов равна длине этой дуги. Иными слова-

ми, если и — постоянные пометки узлов i и j соответственно, то условие, при выполнении которого эти узлы принадлежат кратчайшей цепи, может быть записано следующим образом:

Это соотношение можно использовать рекурсивно, двигаясь от узла t к узлу s. Определив узел, непосредственно предше­ствующий t в кратчайшей цепи, будем повторять данную про­цедуру до тех пор, пока не достигнем узла s. Можно показать, что кратчайшая цепь в рассмотренной нами сети образуется последовательностью узлов s —1—2—6—4—5— t.

*Для заданного узла j через будем обозначать оценку длины кратчайшей цепи из источника s в узел j. Если эта оценка не может быть улучшена, то соответствующее значение мы назовем «постоянной пометкой» и будем обозначать ее символом .

В противном случае назовем его «временной пометкой». Вначале процедуры постоянная пометка приписывается только источнику. Каждая другая пометка является временной и ее величина равна длине дуги, ведущей из источника в соответствующий узел. Для определения ближайшего к источнику узла выберем временную пометку с минимальным значением и объявим ее постоянной пометкой.

ПРИЛОЖЕНИЕ 4

Дата добавления: 2014-01-07