=====324
@Рис. 12.8. Дерево кратчайшего маршрута
Алгоритмы установки и коррекции меток, описанные в следующих разделах, используют похожие классы для представления узлов и связей. Класс узла включает поле Dist, которое определяет расстояние от корня до узла в растущем дереве кратчайшего маршрута. В алгоритме установки меток, после вставки узла в дерево полю Dist присваивается правильное значение, и оно в дальнейшем не меняется. В алгоритме коррекции меток, значение поля Dist может понадобиться обновить, если алгоритм заменит связь.
Класс узла также включает поле NodeStatus, которое указывает, находится ли узел в дереве кратчайшего маршрута, списке возможных связей, или ни в одной из этих структур. Поле InLink указывает на связь, которая ведет к узлу в дереве кратчайшего маршрута.
Public Id As Integer
Public X As Single
Public Y As Single
Public Links As Collection
Public Dist As Integer ' Расстояние от корня дерева пути.
Public NodeStatus As Integer ' Статус дерева маршрута.
Public InLink As PathSLink ' Связь, ведущая к узлу.
======325
Используя поле InLink, программа может перечислить узлы в пути от корня до узла I в обратном порядке при помощи следующего кода:
Dim node As PathSNode
Set node = I
Do
' Вывести узел.
Print node.Id
If node Is Root Then Exit Do
' Перейти к следующему узлу вверх по дереву.
If node.IsLink.Node1 Is node Then
Set node = node.InLink.Node2
Else
Set node = node.InLink.Node1
End If
Loop
Класс link в алгоритме включает поле InPathTree, которое указывает, является ли связь частью дерева кратчайшего маршрута.
Public Node1 As PathSNode
Public Node2 As PathSNode
Public Cost As Integer
Public InPathTree As Boolean
Оба алгоритма установки и коррекции меток используют список возможных связей, в котором находятся связи, которые могут быть добавлены в дерево кратчайшего маршрута, но они по‑разному оперируют этим списком. Алгоритм установки меток всегда выбирает связь, которая обязательно окажется частью дерева кратчайшего маршрута. Алгоритм коррекции меток выбирает элемент, который находится на вершине списка.
В начале этого алгоритма значения поля 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
Узкое место этого алгоритма заключается в поиске узла с наименьшим значением поля Dist в списке возможных узлов. Некоторые варианты этого алгоритма используют другие структуры данных для хранения списка возможных узлов. Например, можно было бы использовать упорядоченный связный список. При использовании этого метода потребуется только один шаг для того, чтобы найти следующий узел, который будет добавлен к дереву кратчайшего маршрута. Этот список будет всегда упорядоченным, поэтому узел на вершине списка всегда будет искомым узлом.
Это облегчит поиск нужного узла в списке, но усложнит добавление узла в него. Вместо того чтобы просто помещать узел в начало списка, его придется поместить в нужную позицию.
Иногда также требуется перемещать узлы в списке. Если в результате добавления узла в дерево кратчайшего маршрута уменьшилось кратчайшее расстояние до другого узла, который уже был в списке, то нужно переместить этот элемент ближе к вершине списка.
Предыдущий алгоритм и этот его новый вариант представляют собой два крайних случая управления списком возможных узлов. Первый алгоритм совсем не упорядочивает список и тратит достаточно много времени на поиск узлов в сети. Второй тратит много времени на поддержание упорядоченности списка, но может очень быстро выбирать из него узлы. Другие варианты используют промежуточные стратегии.
Например, можно использовать для хранения списка возможных узлов приоритетную очередь на основе пирамид, тогда можно будет просто выбрать следующий узел с вершины пирамиды. Вставка нового узла в пирамиду и ее переупорядочение будет выполняться быстрее, чем аналогичные операции для упорядоченного связного списка. Другие стратегии используют сложные схемы организации блоков для того, чтобы упростить поиск возможных узлов.