Кратчайшие пути

1.

ИСО
КРАТЧАЙШИЕ ПУТИ
Пусть G (V , E ) ориентированный граф, дугам которого приписаны веса w(e), e E,
интерпретируемые как длины дуг. Если между вершинами существует путь, то его длина
определяется как сумма длин составляющих его дуг. Рассмотрим следующие задачи:
1) для двух выделенных вершин s,t V требуется выбрать путь из s в t минимальной длины;
2) для выделенной вершины s V необходимо найти пути минимальной длины до всех
остальных вершин графа;
3) для каждой пары вершин графа требуется найти кратчайший путь.
Задача 1 не имеет решения, если в графе существует контур отрицательной длины и путь из s в t,
содержащий вершину контура. Задача 2 не имеет решение при наличии контура отрицательной
длины и существования пути из s в какую-либо вершину контура. Задача 3 не имеет решения при
наличии контура отрицательной длины. Поэтому алгоритмы решения задач должны либо
обнаруживать наличие контуров отрицательной длины, либо применяться для графов заведомо не
содержащих таких контуров.
Все алгоритмы нахождения кратчайших путей основаны на принципе динамического
программирования, который применительно к данной задаче означает, что путь
s , … , x , … ,t
является кратчайшим от вершины s к вершине t тогда и только тогда, когда путь
s,…,x
является кратчайшим от вершины s к вершине x, а путь
x,…,t
является кратчайшим от вершины x к вершине t.

2.

ИСО
Алгоритм Дейкстры применяется для поиска решения в задачах 1,2 при w(e) ≥ 0, e E.
Алгоритм основан на присвоении вершинам меток. Первая часть метки l (u) вершины u
указывает текущее кратчайшее растояние от вершины s до вершины u, вторая –
предшествующую вершину в текущем пути от вершины s до вершины u. Метки могут быть
временными или постоянными. Постоянная метка не может изменяться в процессе
выполнения алгоритма.
Для вершины p V пусть O+( p ) = { x V | ( p , x ) E }.
Шаг 1. Положить метку вершины s равной (0 , s) и считать эту метку постоянной. Для всех
вершин u ≠ s положить метки равными (∞,s) и считать эти метки временными. За текущую
рассматриваемую вершину с постоянной меткой взять вершину p = s.
Шаг 2. Для каждой вершины u O+( p ) с временной меткой изменить метку в соответствии со
следующим выражением: l ( u ) = min [ l ( u ), l ( p ) + w ( p, u ) ]. При этом, если первая часть метки
изменилась, то изменить вторую часть метки, положив её равной p.
Шаг 3. Среди всех вершин с временными метками найти вершину u с минимальной первой
частью l ( u ) метки.
Шаг 4. Считать метку вершины u постоянной и положить p=u .
Шаг 5(a ). (При нахождении пути от s к t). Если p = t, то l ( t ) является длиной кратчайшего пути
от s к t. Алгоритм завершает работу. Если p ≠ t , перейти к шагу 2.
Шаг 5(б). (При нахождении путей от s ко всем вершинам). Если все вершины помечены
постоянными метками, то эти метки дают длины кратчайших путей. Алгоритм завершает работу.
Если некоторые метки являются временными, то перейти к шагу 2.

3.

ИСО
По завершении алгоритма первые части меток дают искомые кратчайшие расстояния. Сами
кратчайшие пути можно получить с помощью рекурсивной процедуры, начиная с вершины t ,
для которой ищется кратчайший путь от s . Вторая часть метки вершины t указывает вершину u
непосредственно предшествует ей в кратчайшем пути от s к t. Берём вторую часть метки
вершины u и повторяем действия, пока не достигнем вершины s.
Сложность алгоритма Дейкстры равна О ( |V |2 ).
Пример.
x1
9
5
x2
2
1
3
8
s
6
t
x3
3
2
4
x4
s
( 0, s )*
x1
( , s )
( 5, s )
( 5, s )*
5
1
x5
x2
( , s )
( , s )
( , s )
( 14, x1 )
( 6, x3 )*
x3
( , s )
( 8, s )
( 5, x4 )
( 5, x4 )*
x4
( , s )
( 3, s )*
x5
( , s )
( , s )
( 7, x4 )
( 7, x4 )
( 7, x4 )
( 7, x4 )*
t
( , s )
( , s )
( , s )
( , s )
( 11, x3 )
( 9, x2 )
( 8, x5 )*

4.

ИСО
Теорема. Алгоритм Дейкстры корректен.
Доказательство проведем индукцией по номеру итерации. Для первой итерации (присвоении
постоянной метки исходной вершине) l(s)=0, что совпадает с кратчайшим расстоянием. Пусть
выполняется очередная итерация и постоянную метку l ( u ) получает вершина u.
Соответствующий путь S из s в u по алгоритму имеет только вершины с постоянными метками.
Предположим, что l ( u ) не кратчайшее расстояние. Тогда существует путь
P ={s , … , x , y , … , q , u} из s в u, длина которого d(P) < l ( u ). Путь P не может включать только
вершины с постоянными метками. Так как по правилам алгоритма l ( u ) минимальная метка,
выбираемая на итерации среди таких путей. И следовательно l ( u ) даёт длину кратчайшего
пути из s в u среди путей использующих только вершины, получивших постоянные метки до
рассматриваемой итерации. Пусть y первая вершина в пути P, имеющая не постоянную метку, а
x ей предшествующая с постоянной меткой (такая вершина найдётся, хотя бы s). Имеем
l(u) ≤ l(y) ≤ d(s,u), иначе y не является вершиной кратчайшего пути. Здесь d(s,u) – длина
кратчайшего расстояния от s до u. С другой стороны d(s,u) ≤ l(u), что и доказывает равенство
d(s,u) = l(u).

5.

ИСО
Алгоритм Форда-Беллмана применяется для решения задачи 2. Ограничений на длину дуг
не накладывается. Алгоритм позволяет определить наличие контура отрицательной длины
в графе.
Пронумеруем вершины исходного графа номерами от 1 до n = | V | , причём вершине s
присвоим первый номер. Составим матрицу расстояний D = | dij |nxn для исходного графа,
Положив
0, i j ,
dij w ( xi , x j ) , ( xi , x j ) E ,
, ( xi , x j ) E
Так же как в алгоритме Дейкстры будем присваивать вершине xi метку ( lk ( xi ) , xk ) , где
lk ( xi ) – кратчайшее расстояние от вершины x1 до вершины xi , по всем путям содержащим
не более чем k дуг, xk – вершина предшествующая xi в кратчайшем пути, содержащим не
более чем k дуг.

6.

И СО
Шаг 1. Положить k = 1, l1 ( xi ) = d1i , вторую часть метки для всех вершин равной x1 .
Шаг 2. Найти lk + 1 ( xi ) = min { lk ( xi ) , min (lk ( x j ) d ji )
1 j n
} для всех i = 1 ,…, n .
При lk + 1 ( xi ) ≠ lk ( xi ) вторая часть метки вершины xi полагается равной вершине на которой
достигается
min (lk ( x j ) d ji )
1 j n
.
Шаг 3. Если lk + 1 ( xi ) ≠ lk ( xi ) для некоторой вершины xi и k + 1 ≤ n , то полагаем k := k + 1 и
возвращаемся к шагу 2.
Если lk + 1 ( xi ) ≠ lk ( xi ) для некоторой вершины xi и k + 1 = n + 1, то граф имеет контур
отрицательной длины. Задача не имеет решения.
Если lk + 1 ( xi ) = lk ( xi ) для всех i = 1,…, n , и k + 1 ≤ n + 1 , то метки lk + 1 ( xi ) дают кратчайшие
расстояния.
Сами кратчайшие пути строятся также, как в алгоритме Дейкстры по вторым частям меток.
Сложность алгоритма Форда-Беллмана равна О(|V|3 ).

7.

ИСО
x1
2
x2
1
-1
3
1
3
x4
x3
-4
-3
0
1
3
3
0
0
0
-2
2
0
∞
∞
1
0
-4
-4
1
-1
0
-4
3
3
3
3
3
-3
∞
0
3
-1
-1
-1
1 (0,x1)
(1,x1)
(3,x1)
(3,x1)
2 (0,x1)
(0,x4)
(3,x1)
(-1,x3)
3 (0,x1)
(-4,x4)
(3,x1)
(-1,x3)
4 (-2,x2)
(-4,x4)
(3,x1)
(-1,x3)
5 (-2,x2)
(-4,x4)
(1,x1)
(-1,x3)

8.

Алгоритм Флойда
Применяется для решения задачи 3. Ограничений на длины дуг не накладывается. Алгоритм
обнаруживает контур отрицательной длины.
Нумеруем вершины графа номерами от 1 до n = | V | и строим матрицу расстояний
D = | dij |nxn для исходного графа, по аналогии с алгоритмом Форда-Беллмана.
Пусть значение кратчайшего расстояния от вершины xi к вершине xj по всем путям, содержащим
вершины с номерами не более k.
0
0
0
0
Шаг 1. Положить k = 0, и построить матрицы D d ij n n , T tij n n по правилу:
d ij0 d ij , tij0 j , i, j 1, n .
Шаг 2. Построить матрицы D k 1 d ijk 1 , T k 1 tijk 1
, по матрицам
n n
n n
вычисляя их элементы по формулам:
D k d ijk
n n
, T k tijk
n n
d ijk , i k 1, j 1, n ,
tijk , если d ijk 1 d ijk ,
k 1
k
k 1
d ij d ij , j k 1, i 1, n,
tij
k 1
k
j , если d ij d ij .
k
k
k
min { d ij , d ik 1 d k 1 j } , i k 1, j k 1,
k 1
Шаг 3. Если k + 1 ≤ n и для некоторого i элемент d ii 0 , то граф имеет контур отрицательной
длины. Задача не имеет решения.
Если k + 1 < n и
d iik 1 0 , i 1, n , то положить k := k +1 и перейти к шагу 2.
Если k+1 = n и
то матрица Dn даёт кратчайшие расстояния между парами
diik 1 0 , i 1, n ,
вершин.
Сложность алгоритма Флойда равна О(|V|3 ).

9.

Алгоритм Флойда
Пример.
2
x2
x1
1
-1
3
1
3
x4
x3
-3
4
0 1 3 3
1
2 0
1
D0
, T0
1 1 0 4
1
3 3 0
1
2
2
2
2
3
3
3
3
4
4
,
4
4
0 1
2 0
D1
1 1
3 3
1
1
, T1
1
1
2
2
2
2
3
1
3
1
4
1
,
4
4
3
5
0
6
3
5
4
0
0
1
2
0
D2
1 1
1 3
3
5
0
2
3
1
5
1
, T2
4
1
0
2
2
2
2
2
3
1
3
2
4
1
,
4
4
0
1
2
0
D3
1 1
1 3
3
5
0
2
3
1
5
1
, T3
4
1
0
2
2
2
2
2
3
1
3
2
4
1
,
4
4
0
0
2
0
D4
1 1
1 3
3
5
0
2
3
1
5
1
, T4
4
1
0
2
4
2
2
2
3
1
3
2
4
1
.
4
4

10.

Исследование операций
Задача о кратчайшем пути с фиксированными платежами.
Задача возникает в случае, когда за прохождение через узлы (вершины) сети взимается штраф
или плата. Например плата взимаемая за вход судна в порт, стоянку транспорта в терминалах
разгрузки.
Рассмотрим задачу в терминах «штраф за выполнение поворота». Штраф за выполнение
поворота зависит от направления движения въезде на перекрёсток и направления движения
при выезде с перекрёстка.
1
въезд
1
3
2
3
1
5
2
3
3
2
4
6
2
3
3
4
6
Пусть штраф за поворот равен 3. Если поворота нет, то штраф равен 0.
7
3
3
выезд
8

11.

Исследование операций
1
въезд
1
3
2
3
1
5
2
3
3
2
4
6
2
3
3
4
6
7
3
3
выезд
8
P1
(1,2) (2,5)
(5,6)
(6,7)
(7,8)
Сумма
Дл.дуг
1
3
1
6
3
14
Штраф
0
0
0
0
3
3
P2
(1,2) (2,5)
(5,6)
(6,4)
(4,8)
Дл.дуг
1
3
1
2
4
11
Штраф
0
0
0
3
3
6
P3
(1,2) (2,3)
(3,4)
(4,8)
Дл.дуг
1
2
2
4
9
Штраф
0
3
3
0
6
Общие
17
17
15

12.

Исследование операций
В сети со штрафами за выполнение поворотов кратчайший путь по общим затратам из s в t ,
проходящий через промежуточную вершину k , может не содержать в себе кратчайший путь по
общим затратам из s в k или кратчайший путь из k в t . В нашем примере кратчайший по общим
затратам путь P3 (1->2->3->4->8) имеет часть 1->2->3->4 с общими затратами 11, которая
является не минимальной по общим затратам. В пути P2 (1->2->5->6->4->8) из 1 в 4 по части
1->2->5->6->4 затраты составляют 10.
1
въезд
1
3
2
3
1
5
2
3
3
2
4
6
2
3
3
4
6
7
3
3
выезд
8
Алгоритм. Пусть дана сеть G=(V,E) с n вершинами и m дугами и выделенными вершинами s и t .
Шаг 1. Вводим фиктивные вершины s и t и дуги (s, s), (t, t) . Длины дуг полагаем равными 0.
Шаг 2. Дуги сети помечаем метками L0 , L1 , … , Lm+1 . L0 соответствует (s,s) , Lm+1 - (t,t) .
Шаг 3. Строим фиктивную сеть с m+2 вершинами L0 , L1 , … , Lm+1 . Вершину Li соединяем дугой с
вершиной Lj тогда и только тогда, когда Li непосредственно предшествует в исходной сети Lj .
Длину этой дуги полагаем равной d(Li)+p( Li , Lj ) , где p( Li , Lj ) – штраф за поворот.
Шаг 4. Решаем задачу о кратчайшем пути от вершины L0 до вершины Lm+1 .

13.

Исследование операций
1
въезд
1
3
2
3
1
2
3
L1
s
5
2
3
L0
1
4
L2
2
6
6
2
3
3
4
L3
5
L7
0
1
выезд
8
L4
7
L5
L9
4
2
4
3
4
1
3
5
8
4
9
5
5
6
7
3
L6
3
1
3
6
L8
0
7
8
L10
t
3
10
4
9
2