Дийкстры алгоритм

Этот алгоритм сначала был представлен в [DIJK59]. Более современная интерпретация и доказательство правильности может быть найдено в [CORM90]. Здесь будет дано краткое описание алгоритма вместе с некоторыми замечаниями относительно свойств этого алгоритма, но без доказательств или теоретических выводов.

Дан граф G = (V, E) и исходная вершина sÎV. Здесь V множество вершин и E множество граней в G. Далее мы имеем функцию веса грани w(u,v) ? 0 "(u,v)ÎE. Алгоритм делит все вершины V, на два непересекающихся множества V = R È Q. Множество R, содержит такие вершины, чьи веса в заключительном наиболее коротком пути были определены и множество Q=V-R. Когда вершина перемещается из Q в R, мы говорим, что она 'удаляется'. Некоторые описания алгоритма называют Q 'открытым' множеством и R 'закрытым' множеством. Для каждой вершины v, мы храним оценочное значение минимума для самого короткого пути, g[v]. Поскольку мы заинтересованы вовсе не в нахождении наименьшего значения стоимости пути, а скорее фактического множества вершин, которая составляет этот путь, мы также сохраняем, для каждой вершины грань предшественника, ed[v], которая является гранью исходящей от соседней вершины в текущем самом наилучшем пути от рассматриваемой вершины. Этот массив может затем использоваться, чтобы восстановить путь по указателям возврата от вершины адресата, см. 4.2.3. В случае, если имеется более чем один оптимальный путь, только последний обнаруженный путь будет запомнен согласно этому алгоритму. В разделе 4.2.5 описан, способ чтобы изменить это, дабы 'выбрать' более визуально приятный путь в таких случаях неоднозначности.

The algorithm, in pseudo-code, proceeds as follows:

Алгоритм на псевдокоде:

Dijkstra(G,w,s) - граф, функция стоимости, исходная вершина

R = Q = {} - пока в обоих множествах ничего нет

for all vÎV do - для всех вершин надо кое-что вычислить J

g[v] = ¥ - инициализация стоимости пути

Q.Insert(v) - вставим вершину в открытое множество

( здесь должна быть вставка в Q вершины s со стоимостью 0 )

while (Q ? {}) do - пока есть точки в открытом множестве

u = Q.ExtractMin() - извлечь вершину с минимальной стоимостью - u

R = R È {u} - занести в закрытое множество

for vÎNeighbors{u} do - для всех соседей вершины u

if (g[v] > g[u] + w(u,v)) then - если стоимость соседа v больше,

чем стоимость грани +

стоимость вершины u, то

Q.DecreaseKey(v, g[u] + w(u,v)) - установить стоимость

вершины v

ed[v] = (u,v) - и присвоить указатель возврата с v -> u

Множество Q должно быть выполнено в виде приоритетной очереди со следующими операциями: Q.Insert (u) - вставляет вершину в очередь, Q.ExtractMin () - извлекает и удаляет элемент vÎQ с самым маленьким g[v], Q.DecreaseKey(v, a) - уменьшает ( присваивает ) g[v] к a, и обновляет очередь.

Алгоритм работает при помощи повторяющегося извлечения вершины vÎQ с минимальной стоимостью самого короткого пути, g[v].

Для практической реализации, мы можем разделить Q на два непересекающихся подмножества, U и PQ, где, для того чтобы стартовать, U содержит все вершины за исключением s, и PQ используется вместо Q выше. Вершины затем перемещаются из U в PQ, когда они первый раз были посещены. Мы можем использовать некоторый флаг, для того чтобы обозначать, была ли вершина ранее посещена или нет (то есть если она находится в U) и таким образом не должно сохраняться в U явно. Всегда хранение приоритетной очереди PQ как можно меньшего размера, может быть очень полезно для быстродействия; см. 4.2.5.

7.2.2