Алгоритм Дейкстры (случай неотрицательной матрицы весов)
Наиболее эффектный алгоритм решения задачи о кратчайшем (s-t)-пути первоначально дал Дейкстра. Этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от s к этой вершине.
Значения пометок постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине.Описание алгоритма Дейкстра:
Пусть 
- пометка вершины 
.
Шаг 1. Положить 
и считать эту пометку постоянной. Положить 
для всех 
и считать эти пометки временными. Положить 
.
Шаг 2. Для всех 
, пометки которых временные, изменить пометки в соответствии со следующим выражением:
(1.1)
Шаг 3. Среди всех вершин с временными пометками найти такую, для которой 
.
Шаг 4. Считать пометку вершины 
постоянной и положить 
.
Шаг 5.
1. Если 
, то 
является длиной кратчайшего пути. Если 
, перейти к шагу 2 (для случая поиска пути от s к t.)
2. Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Если некоторые пометки являются временными перейти к шагу 2 (для случая поиска путей от s ко всем остальным вершинам).
Как только длины кратчайших путей от s будут найдены, то сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения (1.2). Так как вершина 
непосредственно предшествует вершине в кратчайшем пути от s к , то для любой вершины 
соответствующую вершину можно найти как одну из оставшихся вершин, для которой
. (1.2)
Если кратчайший путь от s до любой вершины является единственным, то дуги 
этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько "кратчайших" путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине 
соотношение (2) будет выполняться для более чем одной вершины .
), либо таким, что рассматриваются все дуги , входящие в какой-либо из кратчайших путей, и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительно s. Пример
Рассмотрим граф G, изображенный на рис. 1.1, где каждое неориентированное ребро рассматривается как пара противоположно ориентированных дуг равного веса. Матрица весов C приведена ниже.
Рис. 1.1. Граф G.
Требуется найти все кратчайшие пути от вершины 
ко всем остальным вершинам. Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.
| C= | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | |
| x1 | 0 | 12 | 0 | 0 | 0 | 0 | 5 | 2 | 10 | |
| x2 | 12 | 0 | 14 | 0 | 0 | 0 | 4 | 0 | 15 | |
| x3 | 0 | 14 | 0 | 20 | 0 | 25 | 0 | 0 | 9 | |
| x4 | 0 | 0 | 20 | 0 | 2 | 15 | 5 | 0 | 0 | |
| x5 | 0 | 0 | 0 | 2 | 0 | 8 | 0 | 0 | 0 | |
| x6 | 0 | 0 | 25 | 0 | 8 | 0 | 12 | 11 | 10 | |
| x7 | 0 | 4 | 0 | 5 | 0 | 12 | 0 | 0 | 22 | |
| x8 | 2 | 0 | 0 | 0 | 24 | 11 | 0 | 0 | 7 | |
| x9 | 10 | 15 | 0 | 0 | 0 | 10 | 22 | 7 | 0 |
Воспользуемся алгоритмом Дейкстры.
Шаг 1. 
, 
, 
.
Первая итерация
Шаг 2. 
- все пометки временные. Возьмем сначала 
. Из (1.1) получаем
,
аналогично 
, 
, 
.
Шаг 3. 
соответствует 
.
Шаг 4. 
получает постоянную пометку 
, 
.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Пометки в начале следующей итерации показаны на рис. 1.2(а).
Вторая итерация
Шаг 2. 
- все пометки временные. Из соотношения (1.1) имеем
,
аналогично 
, 
. Пометки изображены на рис. 1.2(б).
Шаг 3. 
соответствует 
.
Шаг 4. 
получает постоянную пометку 
, 
.
Шаг 5. Перейти к шагу 2.
Третья итерация
Шаг 2. 
- из соотношения (1.1) получаем
,
и аналогично 
, , .
Шаг 3. 
соответствует 
.
Шаг 4. 
получает постоянную пометку 
, 
.
Шаг 5. Перейти к шагу 2.
Четвертая итерация
Шаг 2. 
- не все пометки временные, поэтому из соотношения (1.1) получаем
,
и аналогично .
Шаг 3. 
соответствует 
.
Шаг 4. получает постоянную пометку 
, 
.
Шаг 5. Перейти к шагу 2.
Пятая итерация
Шаг 2. 
- не все пометки временные, поэтому из соотношения (1.1) получаем
.
Шаг 3. 
соответствует 
.
Шаг 4. 
получает постоянную пометку 
, 
.
Шаг 5. Перейти к шагу 2.
Шестая итерация
Шаг 2. 
- все пометки временные, из соотношения (1.1) получаем
,
и аналогично 
, .
Шаг 3. 
соответствует 
.
Шаг 4. 
получает постоянную пометку 
, 
.
Шаг 5. Перейти к шагу 2.
Седьмая итерация
Шаг 2. 
- не все пометки временные, поэтому из соотношения (1.1) получаем
.
Шаг 3. 
соответствует 
.
Шаг 4. получает постоянную пометку 
, 
.
Шаг 5. Перейти к шагу 2.
Восьмая итерация
Шаг 2. 
- не все пометки временные, поэтому из соотношения (1.1) получаем
.
Шаг 3. 
соответствует 
.
Шаг 4. 
получает постоянную пометку 
, 
.
Шаг 5. Все вершины имеют постоянные пометки. Конец работы алгоритма. Пометки полученные в результате работы алгоритма показаны на рис. 1.2(в).
Найдем кратчайший путь между вершиной и начальной вершиной 
, последовательно используя соотношение (1.2). Таким образом, полагая 
, находим вершину 
, непосредственно предшествующую в кратчайшем пути от к : вершина должна удовлетворять соотношению
.
Единственной такой вершиной является . Далее, применяем второй раз соотношение (1.2), беря 
; получаем вершину 
, непосредственно предшествующую в кратчайшем пути от к . Вершина удовлетворяет соотношению
.
Единственной такой вершиной является и поэтому кратчайший путь от к есть 
.
- база, дающая все кратчайшие пути от , представляет собой дерево, изображенное жирными линиями на рис. 1.2 (в).
(а)
(б)
(в)
Рис. 1.2. (а) Пометки в конце 1-й итерации. (б) Пометки в конце шага 2 на 2-й итерации. (в) Окончательные пометки вершин и - база.