ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
149
гда будут просмотрены все вершины и
Q
останется пустым, в
p
[
u
]
окажется кратчайший маршрут, а в
d
[
u
] –
его длина. Псевдокод алго-
ритма представлен ниже:
АЛГОРИТМ ДЕЙКСТРЫ ОКОД(G,s,Q,d,p)
Q=V; d[s]=0; p[s]=0;
ЦИКЛ (для всех вершин u
∈
V & u
≠
s)
d[u]=
∞;
ВСЕ ЦИКЛ
ЦИКЛ ПОКА (
Q
≠∅)
ПОИСК (u
∈
Q
с минимальным значением d[u])
Q=Q\u;
ЦИКЛ (для всех вершин v, v
∈
Adj[u] & v
∈
Q)
ЕСЛИ (d[v]>d[u]+w[u][v]) ТО
d[v]=d[u]+w[u][v];
p[v]=u;
ВСЕ ЕСЛИ
ВСЕ ЦИКЛ
ВСЕ ЦИКЛ
КОНЕЦ
В алгоритме необходимо реализовать структуры данных для хра-
нения графа
G
,
множеств
Q
,
множеств длин путей
w
[
u
]
из вершин к
смежным вершинам, информацию о кратчайших путях
p
[
u
]
и их дли-
нах
d
[
u
]
для каждой вершины. Как говорилось ранее, для вычисли-
тельной системы МКОД требуется представить их в виде таблиц
«
ключ-значение».
Примем следующие обозначения:
S
.
KEY(
k
1
, ..,
k
n
) –
составной ключ
поиска в структуре
S
,
состоящий из полей
k
1
, ..,
k
n
;
S.DATA(
d
1
, ...,
d
n
) –
данные для структуры
S
,
состоящие из полей
d
1
, ...,
d
n
.
Доступ к кон-
кретным полям данных может быть продемонстрирован в псевдокоде
алгоритма с помощью модификатора, т. е. как
S
.
DATA.
d
1
.
Например,
изменение поля
x
в составном поле данных указывается как
S
.
DATA.
x
=10.
Множество
Q
используется для поиска вершины с наименьшим
показателем
d
[
u
].
Поскольку значение
d
[
u
]
для разных вершин в
структуре
Q
может быть одинаковым, то
d
[
u
]
не должен являться
ключом. В качестве ключа может быть выбрана пара значений
Q
.
KEY=(
d
[
u
],
u
).
Это обеспечивает не только поиск вершины с ми-
нимальным
d
[
u
],
но и выбор вершины с наименьшим номером из не-
скольких возможных вариантов. Поле данных структуры
Q
не ис-
пользуется:
Q
.
DATA=(0).
Исходный граф
G
в алгоритме служит для определения списка
смежных вершин и другой информации, соответствующей каждой