Установка меток

В начале этого алгоритма значения поля Dist корневого узла устанавливается равным 0. Затем корневой узел помещается в список возможных узлов, при этом значение поля NodeStatus этого узла принимает значение NOW_IN_LIST, указывая на то, что он находится в списке.

После этого выполняется поиск в списке узла с наименьшим значением Dist. Первоначально это будет корневой узел, так как он единственный в списке.

Затем алгоритм удаляет этот узел из списка, и устанавливает значение поля NodeStatus для этого узла равным WAS_IN_LIST, указывая на то, что этот узел теперь является частью дерева кратчайшего маршрута. Поля Dist и IsLink узла уже имеют правильные значения. Для каждого корневого узла, значение поля IsLink равно Nothing, а значение поля Dist равно нулю.

После этого алгоритм проверяет все связи, выходящие из выбранного узла. Если соседний узел на другом конце связи никогда не находился в списке возможных узлов, то алгоритм добавляет его к списку. Он устанавливает значение поля NodeStatus соседнего узла равным NOW_IN_LIST., а значение поля Dist — расстоянию от корневого узла до выбранного узла плюс цене связи. И, наконец, он присваивает значение полю InLink соседнего узла так, чтобы оно указывало на связь с соседним узлом.

========326

Во время проверки алгоритмом связей, выходящих из выбранного узла, если значение поля NodeStatus соседнего узла равно NOW_IN_LIST, то этот узел уже находится в списке возможных узлов. Алгоритм проверяет текущее значение Dist соседнего узла, проверяя, не будет ли путь через выбранный узел короче. Если это так, то он обновляет поля InLink и Dist соседнего узла и оставляет соседний узел в списке возможных узлов.

Алгоритм повторяет этот процесс, удаляя узлы из списка возможных узлов, проверяя соседние с ними узлы и добавляя соседние узлы в список до тех пор, пока список не опустеет.

На рис. 12.9 показана часть дерева кратчайшего маршрута. В этой точке алгоритм проверил узлы A и B, удалил их из списка возможных узлов, и проверил их связи. Узлы A и B уже добавлены к дереву кратчайшего маршрута, и теперь в списке возможных узлов находятся узлы C, D и E. Жирные стрелки на рис. 12.9 соответствуют значениям полей InLink узлов в этой точке. Например, значение поля InLink для узла E соответствует связи между узлами E и B.

После этого алгоритм ищет в списке возможных узлов узел с наименьшим значением Dist. В данной точке значения полей Dist узлов C, D и E равны 10, 21 и 22 соответственно, поэтому алгоритм выбирает узел C. Узел C удаляется из списка возможных узлов, и его полю NodeStatus присваивается значение WAS_IN_LIST. Теперь узел C является частью дерева кратчайшего маршрута, и его поля Dist и InLink имеют правильные значения.

Затем алгоритм проверяет связи, выходящие из узла C. Единственная связь, выходящая из узла C, идет к узлу E, который уже содержится в списке возможных узлов, поэтому алгоритм не добавляет его в список снова.

Текущий кратчайший маршрут от корня в узел E — это путь A, B, E, полная цена которого равна 22. Но цена пути A, C, E равна всего 17., что меньше, чем текущая цена 22, поэтому алгоритм обновляет значение InLink для узла E, и присваивает полю Dist этого узла значение 17.

@Рис. 12.9. Часть дерева кратчайшего маршрута

=========327

Private Sub FindPathTree(root As PathSNode)

Dim candidates As New Collection

Dim i As Integer

Dim best_i As Integer

Dim best_dist As Integer

Dim new_dist As Integer

Dim node As PathSNode

Dim to_node As PathSNode

Dim link As PathSLink

If root Is Nothing Then Exit Sub

' Сбросить значения полей Marked и NodeStatus всех узлов,

' и флаги Used и InPathTree всех связей.

ResetPathTree

' Начать с корня дерева кратчайшего маршрута.

root.Dist = 0

Set root.InLink = Nothing

root.NodeStatus = NOW_IN_LIST

candidates.Add root

Do While candidates.Count > 0

' Найти ближайший к корню узел‑кандидат.

best_dist = INFINITY

For i = 1 To candidates.Count

new_dist = candidates(i).Dist

If new_dist < best_dist Then

best_i = i

best_dist = new_dist

End If

Next i

' Добавить узел к дерева кратчайшего маршрута.

Set node = candidates(best_i)

candidates.Remove best_i

node.NodeStatus = WAS_IN_LIST

' Проверить соседние узлы.

For Each link In node.Links

If node Is link.Node1 Then

Set to_node = link.Node2

Else

Set to_node = link.Node1

End If

If to_node.NodeStatus = NOT_IN_LIST Then

' Узел раньше не был в списке возможных

' узлов. Добавить его в список.

candidates.Add to_node

to_node.NodeStatus = NOW_IN_LIST

to_node.Dist = best_dist + link.Cost

Set to_node.InLink = link

ElseIf to_node.NodeStatus = NOW_IN_LIST Then

' Узел находится в списке возможных узлов.

' Обновить значения его полей Dist и inlink,

' если это необходимо.

new_dist = best_dist + link.Cost

If new_dist < to_node.Dist Then

to_node.Dist = new_dist

Set to_node.InLink = link

End If

End If

Next link

Loop

GotPathTree = True

' Пометить входящие узлы, чтобы их было проще вывести на экран.

For Each node In Nodes

If Not (node.InLink Is Nothing) Then _

node.InLink.InPathTree = True

Next node

' Перерисовать сеть.

DrawNetwork

End Sub

Важно, чтобы алгоритм обновлял поля InLink и Dist только для узлов, в которых поле NodeStatus равно NOW_IN_LIST. Для большинства сетей нельзя получить более короткий путь, добавляя узлы, которые не находятся в списке возможных узлов. Тем не менее, если сеть содержит цикл, полная длина которого отрицательна, алгоритм может обнаружить, что можно уменьшить расстояние до некоторых узлов, которые уже находятся в дереве кратчайшего маршрута, при этом две ветви дерева кратчайшего маршрута окажутся связанными друг с другом, так что оно перестанет быть деревом.

На рис. 12.10 показана сеть с циклом отрицательной цены и «дерево» кратчайшего маршрута, которое получилось бы, если бы алгоритм обновлял цену узлов, которые уже находятся в дереве.

=======329

@Рис. 12.10. Неправильное «дерево» кратчайшего маршрута для сети с циклом отрицательной цены

Программа PathS использует этот алгоритм установки меток для вычисления кратчайшего маршрута. Она аналогична программам NetEdit и Span. Если вы не вставляете или не удаляете узел или связь, то можно выбрать узел при помощи мыши и программа при этом найдет и выведет на экран дерево кратчайшего маршрута с корнем в этом узле. На рис. 12.11 показано окно программы PathS с деревом кратчайшего маршрута с корнем в узле 3.

@Рис. 12.11. Дерево кратчайшего маршрута с корнем в узле 3

=======330