Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200

• Название: Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
• Анкор: Дискретная Математика
• Дата: 15.09.2022
• Размер: 6.37 Mb.
• Имя файла: S_D_Shaporev_-_Diskretnaya_matematika_-_2004.pdf
• Тип: Учебное пособие; #679116
• страница: 14 из 26

3.10. Нахождение кратчайших путей. Алгоритм Дейкстры

Рассмотрим еще несколько алгоритмов нахождения кратчайшего пути между двумя заданными вершинами в ориентированной сети. Пусть




,
,U
S
G
- ориентированный граф со взвешенными дугами. Обозначим s - вершину - начало пути и t - вершину – конец пути.
Общий подход к решению задачи о кратчайшем пути был развит американским математиком Ричардом Беллманом

, который предложил название динамическое программирование. Задача о кратчайшем пути частный случай следующей задачи: найти в заданном графе пути, соединяющие две заданные вершины и доставляющие минимум или максимум некоторой аддитивной функции, определенной на путях. Чаще всего эта функция трактуется как длина пути и задача называется задачей о кратчайших путях. Алгоритм
Дейкстры одна из реализаций этой задачи. Его часто называют алгоритмом расстановки меток. В процессе работы этого алгоритма узлам сети
S
x
i

приписываются числа (метки)
 
i
x
d
, которые служат оценкой длины (веса) кратчайшего пути от вершины s к вершине
i
x .
Если вершина
i
x получила на некотором шаге метку
 
i
x
d
, это означает, что в графе G существует путь из s в
i
x , имеющий вес
 
i
x
d
. Метки могут находиться в двух состояниях – быть временными или постоянными. Превращение метки в постоянную означает, что кратчайшее расстояние от вершины s до соответствующей вершины найдено.
Алгоритм Дейкстры содержит одно ограничение – веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом этапе находится длина кратчайшего пути, на втором – строится сам путь от вершины s к вершине t .
Этап 1. Нахождения длины кратчайшего пути.
Шаг 1. Присвоение вершинам начальных меток.
Полагаем
 


0
s
d
и считаем эту метку постоянной (постоянные метки помечаются сверху звездочкой). Для остальных вершин
s
x
S
x
i
i


,
полагаем
 


i
x
d
и считаем эти метки временными. Пусть
x
s
x

,


- обозначение текущей вершины.
Шаг 2. Изменение меток.
Для каждой вершины
i
x с временной меткой, непосредственно следующей за вершиной x , меняем ее метку в соответствии со следующим правилом:
 
   




,

ω

,
min
i
i
стар
i
нов
x
x
x
d
x
d
x
d


(3.10.1)
Шаг 3. Превращение метки из временной в постоянную.
Из всех вершин с временными метками выбираем вершину

j
x с наименьшим значением метки
 
 
 










временная
,
min
j
j
j
j
x
d
S
x
x
d
x
d
(3.10.2)
Превращаем эту метку в постоянную и полагаем



j
x
x
Шаг 4. Проверка на завершение первого этапа.
Если
t
x


, то
 
x
d - длина кратчайшего пути от
s до t . В противном случае происходит возвращение ко второму шагу.

Едсгер Дейкстра (1930 - 2002) – нидерландский математик.

Ричард Эрнест Беллман (1920 – 1984) – американский математик.

67
Этап 2. Построение самого кратчайшего пути.
Шаг 5. Последовательный поиск дуг кратчайшего пути.
Среди вершин, непосредственно предшествующих вершине x с постоянными метками, находим вершину
i
x , удовлетворяющую соотношению
   



,
ω

x
x
x
d
x
d
i
i


(3.10.3)
Включаем дугу


x
x
i

,
в искомый путь и полагаем

i
x
x

Шаг 6. Проверка на завершение второго этапа.
Если
s
x


, то кратчайший путь найден – его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.
Пример 1. Задана весовая матрица

сети G . Найти минимальный путь из вершины
1
x в вершину
6
x по алгоритму Дейкстры.
3
x




13
,
 


6
,
7 8 9




15
,
 

0 6 4
x 5
 


9
,
6
x
1
x 9 2
x 6 11 6 6 4




11
,
5
x
Рис. 3.29.
На рисунке 3.29 изображен сам граф по данной матрице весов. Поскольку в данном графе есть цикл между вершинами
2
x ,
3
x и
5
x , то вершины графа нельзя упорядочить по алгоритму Фалкерсрна. На рисунке графа ременные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.
Этап 1. Шаг 1. Полагаем
 
1 1

,
0
x
x
x
d



,
 
 
 
 
 
6 5
4 3
2






x
d
x
d
x
d
x
d
x
d
1-я итерация. Шаг 2. Множество вершин, непосредственно следующих за
1

x
x

с временными метками


,
,

5 4
2
x
x
x
S

Пересчитываем временные метки этих вершин
 


 


 


11 11 0
,
min
,
6 6
0
,
min
,
9 9
0
,
min
5 4
2















x
d
x
d
x
d
Шаг
3.
Одна из временных меток превращается в постоянную


 

,
6 11,
6,
,
,
9
min
4 4
x
x
x
d






Шаг 4.
6 4

x
t
x
x



, происходит возвращение на второй шаг.
2-я
итерация.
Шаг
2.

  


9 5
6
,
9
min
,
,
,

2 5
3 2





x
d
x
x
x
S
,
 


13 7
6
,
min
3





x
d
,
 


11 6
6
,
11
min
5




x
d
Шаг 3.
       




 

,
9 11,
13,
,
9
min
,
,
,
min
2 2
6 5
3 2
x
x
x
d
x
d
x
d
x
d
x
d






Шаг 4.
6 2
x
x

, возвращение на второй шаг.
3-я итерация. Шаг 2.
   


13 8
9
,
13
min
,

3 3





x
d
x
S
Шаг 3.
     




 

,
11 11,
13,
min
,
,
min
5 5
6 5
3
x
x
x
d
x
d
x
d
x
d






Шаг 4.
6 5
x
x

, возвращение на второй шаг.
4-я итерация. Шаг 2.
   


15 4
11
,
min
,

6 6






x
d
x
S
Шаг 3.
   




 

,
13 5
1 13,
min
,
min
3 3
6 3
x
x
x
d
x
d
x
d





Шаг 4.
6 3
x
x

, возвращение на второй шаг.
5-я итерация. Шаг 2.
   


15 9
13
,
15
min
,

6 6





x
d
x
S
4 6
6 7
5 9
6 8
11 6
9 6
5 4
3 2
1 6
5 4
3 2
1













































x
x
x
x
x
x
x
x
x
x
x
x

68
Шаг 3.
 


 

,
15 15
min min
6 6
x
x
x
d




Шаг 4.
,
6 6
x
t
x


конец первого этапа.
Этап 2. Шаг 5. Составим множество вершин, непосредственно предшествующих
6

x
x

с постоянными метками


,

5 3
x
x
S

Проверим для этих двух вершин выполнение равенства (3.10.3).
 
 

  
 


,
ω
9 13 15

,
,
ω
4 11 15

6 3
3 6
5 5
x
x
x
d
x
d
x
x
x
d
x
d












Включаем дугу


6 5
, x
x
в кратчайший путь.
5

x
x

Шаг 6.
1

x
s
x


, возвращение на пятый шаг.
2-я итерация. Шаг 5.


,

4 1
x
x
S

 
 

  
 


,
ω
6 6
11

,
,
ω
11 0
11

5 4
4 5
1 1
x
x
x
d
x
d
x
x
x
d
x
d












Включаем дугу


5 1
, x
x
в кратчайший путь.
1

x
x

Шаг 6.
1

x
s
x


, завершение второго этапа.
Итак, кратчайший путь от вершины
1
x до вершины
6
x построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг

 

,
,
μ
6 5
5 1
x
x
x
x


3.11. Нахождение кратчайших путей. Алгоритм Беллмана - Мура

Если веса – произвольные числа и граф G не содержит ориентированных циклов отрицательного веса, то минимальный путь может быть найден алгоритмом Беллмана –
Мура, похожим на алгоритм Дейкстры. Этот алгоритм часто называют алгоритмом корректировки меток. Как и в алгоритме Дейкстры всем вершинам приписываются метки, однако здесь нет деления меток на временные и постоянные. Корректировка меток осуществляется по старому правилу (3.10.1), однако выполнение условия (3.10.2) теперь не гарантирует, что длина кратчайшего пути от s до
j
x
найдена, так как наличие в графе G дуг с отрицательными весами может уменьшить эту метку на последующих шагах. Поэтому в алгоритме Беллмана – Мура вместо процедуры превращения временной метки в постоянную формируется очередь вершин, которые нужно просмотреть для анализа возможности уменьшения по правилу (3.10.1) меток вершин, не находящихся в данный момент в очереди, но достижимых из нее за один шаг. В процессе работы алгоритма одна и та же вершина может несколько раз вставать в очередь, а затем покидать ее.
Алгоритм Беллмана – Мура состоит из двух этапов. На первом этапе находятся длины кратчайших путей от вершины s до всех остальных вершин графа. Этот этап заканчивается при отсутствии вершин в очереди.
Второй этап – построение кратчайшего пути от s до t совпадает с соответствующим этапом в алгоритме Дейкстры и выполняется по формуле (3.10.3). Опишем подробно все шаги алгоритма.
Этап 1. Нахождение длин кратчайших путей от вершины s до всех остальных вершин графа.
Шаг 1. Присвоение начальных значений.
 
 
,

,
,
,
0
s
x
S
x
x
d
s
d
j
j





 
x
Q


- множество вершин в очереди.
Шаг 2. Корректировка меток и очереди.

Элиаким Гастингс Мур (1862 – 1932) – американский математик.

69
Удаляем из очереди Q вершину, находящуюся в самом начале очереди. Для каждой вершины
i
x , непосредственно достижимой из x , корректируем ее метку по формуле (3.9.1).
Если при этом
 
 
i
стар
i
нов
x
d
x
d

, то корректируем очередь вершин, иначе продолжаем перебор вершин и корректировку временных меток.
Корректировка очереди. Если
i
x не была ранее в очереди и не находится в ней в данный момент, то вершину
i
x ставим в конец очереди. Если же
i
x уже была когда-нибудь ранее в очереди или находится там в данный момент, то переставляем ее в начало очереди.
Шаг 3. Проверка на завершение первого этапа. Если

Q
Ø, то возвращаемся к началу второго шага, если же

Q
Ø, то первый этап закончен, то есть минимальные расстояния от s до всех вершин графа найдены.
Рассмотрим подробный пример 1. Пусть граф G задан весовой матрицей

2
x (∞,4)
5
x (∞,10,5,-3)
6 3 4 -8 7 9 1
x (0) -7 5 6
x (∞,8,0)
6 3
x (∞,11,4) 8 4
x (∞,6,-4)
Рис. 3.30.
На рисунке 3.30 изображен исходный граф по матрице весов. Рассчитаем кратчайший путь от узла
1
x до узла
6
x .
Этап 1. Шаг 1.
 
,
0
,

1 1


x
d
x
x
 
 
,
6
,
2
,
1
x
Q
j
x
d
j




Шаг 2.
 



1 1
\
,

x
Q
Q
x
x
Ø. Пусть S

- множество вершин непосредственно достижимых из вершины x .

  


2 4
2
,
,

x
d
x
x
S


4 4
0
,
min



4<∞? Да.
 
2
x
Q

,
2
x надо было поставить в конец очереди, но Q было пусто, поэтому конец очереди совпал с началом.
 


6 6
0
,
min
4




x
d
?
6


Да.


,
4 2
x
x
Q

Шаг 3.

Q
Ø? Нет. Переход на начало второго шага.
Вторая итерация. Шаг 2.
   


,
,

,

\
,

5 4
3 4
2
x
x
x
S
x
x
Q
Q
x
x




 


11 7
4
,
min
3




x
d
11< ∞? Да.


,
3 4
x
x
Q

 


4 8
4
,
6
min
4




x
d
-4<6? Да. 2бв).


,
3 4
x
x
Q

Вершину
4
x надо поставить в начало очереди, но она уже стоит там.
 


10 6
4
,
min
5




x
d
10<∞? Да.


,
,
5 3
4
x
x
x
Q

Шаг 3.

Q
Ø? Нет, переход на третью итерацию второго шага.
Третья итерация. Шаг 2.
  



,

,
,

\
,

5 3
5 3
4
x
x
S
x
x
x
Q
Q
x
x




 


4 8
4
,
11
min
3




x
d
4<11? Да.


,
5 3
x
x
Q

Вершину
3
x надо поставить в начало очереди, но она уже там.
 


5 9
4
,
10
min
5




x
d
5<10? Да.


,
3 5
x
x
Q

Вершину
5
x
передвигаем из конца очереди в начало.
3 9
8 5
7 6
8 7
6 4
6 5
4 3
2 1
6 5
4 3
2 1
















































x
x
x
x
x
x
x
x
x
x
x
x

70
Шаг 3.

Q
Ø? Нет, переход на четвертую итерацию второго шага.
Четвертая итерация. Шаг 2.
   
 

,

\
,

6 3
5
x
S
x
x
Q
Q
x
x




 


8 3
5
,
min
6




x
d
8< ∞? Да.


,
6 3
x
x
Q

Шаг 3.

Q
Ø? Нет.
Пятая итерация. Шаг 2.
   


,

,

\
,

6 5
6 3
x
x
S
x
x
Q
Q
x
x




 


3 7
4
,
5
min
5




x
d
-3<5? Да.


,
6 5
x
x
Q

 


8 5
4
,
8
min
6



x
d
9<8? Нет.
Шаг 3.

Q
Ø? Нет.
Шестая итерация. Шаг 2.
   
 

,

\
,

6 6
5
x
S
x
x
Q
Q
x
x




 


0 3
3
,
8
min
6




x
d
0<8? Да.
 
6
x
Q

Q содержало только вершину
6
x
и она встала в начало очереди.
Шаг 3.

Q
Ø? Нет.
Седьмая итерация. Шаг 2.
 



x
Q
Q
x
x

\
,

6
Ø.

S

Ø.

70
Шаг 3.

Q
Ø. Конец первого этапа. Найдены минимальные расстояния до всех вершин от первой вершины. Эти расстояния таковы:
 
 
 
,
4
,
4
,
4 4
3 2




x
d
x
d
x
d
 
 
0
,
3 6
5



x
d
x
d