Условие задачи
Найдите кратчайшие маршруты, ведущие из узла A во все другие узлы сети, представленной на рисунке.
Ответ
1-й шаг. Все узлы, которые соединены с узлом А одним ребром метятся следующим образом: Узел В (30, А) и узел С (35, А). Первое число в метке равно расстоянию от помеченного узла до узла А.
Ребро, связывающее узлы А и В, является кратчайшим маршрутом от узла А к узлу В (любой другой маршрут от узла А к узлу В длиннее), и поэтому узлу В приписывается постоянная метка (30, А).
Таким образом по окончании 1-го шага узлы А и В имеют постоянные метки, а узел С временную метку, остальные узлы меток не имеют.
2-й шаг. Отбираются все узлы, которые соединены с узлом В одним ребром и не имеют постоянных мето...