ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
150
вершине. Ключом поиска в структуре
G
является уникальный номер
вершины в графе
G
:
G.KEY=(
u
),
а данными для структуры
G
–
множе-
ство смежных вершин
Adj
[
u
],
массив длин путей для них
w
[
u
],
найден-
ное кратчайшее расстояние
d
[
u
],
маршрут
p
[
u
],
а также бит принад-
лежности вершины к множеству
Q
:
т.е.
G
.
DATA=(
Adj
[
u
],
w
[
u
],
d
[
u
],
p
[
u
],
u
∈
Q
).
Пояснить использование этих структур можно на примере
поиска кратчайших путей для графа, представленного на рис. 2.
а
б
в
Рис. 2. Пример поиска кратчайших путей в графе (начальное состояние
структур данных):
а
–
структура
G
;
б
–
структура
Q
;
в
–
граф
На первом шаге алгоритма из структуры
Q
выбирается мини-
мальный ключ
Q
.
KEY=(0,1) и по нему определяется код
u
,
соот-
ветствующий вершине
s
= 1. Для этой вершины в структуре
G
вы-
бирается строка и определяются поля
Adj
[
u
],
w
[
u
],
d
[
u
],
p
[
u
],
u
∈
Q
.
Найденная строка исключается из структуры
Q
по известному
ключу
Q
.
KEY=(
d
[
u
],
u
).
Далее, для каждой вершины
v
из множества
Adj
[
u
]
по структуре
G
определяется принадлежность к множеству
Q
(
параметр
u
∈
Q
).
Если
u
∈
Q
–
истино, то проверяется условие
d
[
v
]
=
= d
[
u
]
+
w
[
u
][
v
],
где
w
[
u
][
v
] –
один из элементов множества
w
[
u
],
со-
ответствующий ребру между
u
и
v
.
Результат работы алгоритма после
первой итерации показан на рис. 3. Стрелками на графе указаны от-
резки найденного маршрута.
а
б
в
Рис. 3. Пример поиска кратчайших путей в графе (состояние структур
данных после выполнения первой итерации)
а
–
структура
G
;
б
–
структура
Q
;
в
–
граф