Алгоритм Дейкстры поиска кратчайшего пути

Цель работы

Изучить и практически освоить алгоритм Дейкстры поиска кратчайшего пути.

Задание

1. Изучить алгоритм Дейкстры.

2. Используя алгоритм Дейкстры, найти кратчайший путь из вершины s  к вершине t.

 Исходные данные для расчета по двадцати вариантам представлены в таблице 3.2. Вариант задаётся преподавателем: может выбираться, например, по последней цифре номера зачетной книжки или по номеру в групповом журнале.

 

Теоретическая часть

Задача поиска кратчайшего пути наиболее часто встречается на практике. Под кратчайшим путем может пониматься путь минимальной длины, минимальной стоимости или по любым другим весовым коэффициентам, присваиваемым ветвям (ребрам) графа.

 Пусть задан ориентированный граф (рис. 3.1.).

c12 =3

                                                                  

1

2

c2t=2

cs1 =4

                                 

s

t

c14= 2

c4 t =2

c34 =3

cs3 =3

3

4

Рис. 3.1. Ориентированный граф

Пусть длина каждого ребра выражается неотрицательным числом c_ij ≥0.  

Если из i в j нет ребра, то c_ij = ∞.

Алгоритм основан на приписывании узлам временных δ _i  или постоянных весов, равных длине кратчайшего пути из s в t, включающего только вершины с постоянными весами.

 Алгоритм поиска кратчайшего пути из s в t  включает следующие три шага.

Шаг 1. Постоянный вес вершины s = 0 и временные веса δ _j = ∞ для всех j ¹ s. Положим i = s , где i-номер последней вершины с постоянным весом.

Шаг 2. Для каждой вершины с временным весом пересчитываем величину δ _j по следующему выражению

d _j = min { d _j ; d _i + c_ij } .

Присвоим вершине, для которой величина δ _jявляется наименьшей, постоянный вес. Положим i = j .

  

Шаг 3. Если i = t , то кратчайший путь найден. В противном случае переходим к шагу 2.

   Алгоритм Дейкстры позволяет построить дерево кратчайших путей из вершины s во все вершины исходного графа. Для этого шаг 3 нужно изменить следующим образом: если всем вершинам приписаны постоянные веса, то дерево кратчайших путей с корнем в вершине s найдено. В противном случае перейти к шагу 2.

 

Пример реализации алгоритма для графа, приведенного на рис. 3.1.

d S

            Первая итерация

Шаг 1. Присваиваем вершине s постоянный вес     = 0 ; остальным вершинам присваиваем веса δ _j = ∞ ; j =1, 2, 3, 4, t ( j ¹ s ).

Принимаем i = s ; i равно номеру вершины с последним постоянным весом.

Шаг 2. Рассчитаем веса остальных вершин:

d ₁ = min { d ₁ ; d _s + c_s1 } = min { ∞, 0+4 } = 4.

d ₂ = min { d ₂ ; d _s + c_s2 } = min { ∞, 0+∞ } = ∞.

d ₃ = min { d ₃ ; d _s + c_s3 } = min { ∞, 0+3 } = 3.

d ₄ = ∞.

d _t = ∞.

d 3

Минимальный вес имеет вершина 3, ей приписываем постоянный вес                                      =3.

Положим i =3 .

Шаг 3. Так как i = 3 ¹ t, то переходим к шагу 2.

Текущее дерево имеет следующий вид:

Вторая итерация

Шаг 2. Так как найдено новое значение i =3 ¹ t, то пересчитываем временные веса остальных вершин.

d ₁ = min { d ₁ ; d ₃ + c₃₁ } = min { 4, 3+∞ } = 4.

d ₂ = min { d ₂ ; d ₃ + c₃₂ } = min { ∞, 3+∞ } = ∞.

d ₄ = min { d ₄ ; d ₃ + c ₃₄ } = min { ∞, 3+3 } = 6.

         d _t = ∞.

d 1

Минимальный вес имеет вершина 1. Приписываем ей постоянный вес  

     = 4. Положим i =1.

 Шаг 3. Так как i = 1 ¹ t, переходим к шагу 2. Текущее дерево путей имеет следующий вид:

 

     

Третья итерация

      Шаг 2. Так как найдено новое значение i=1 ¹ t , то пересчитываем временные веса вершин.

       d = min { d ₂ ; d ₁ + c₁₂ } =  min { ¥ , 4 + 3 } = 7 ;

       d ₄ = min { d ₄ ; d ₁ + c₁₄ } = min { 6 ,   4 + 2 } = 6 ;

         d   = min { d _t ; d ₁ + c _{1 t} } = ¥ .

d 4

Минимальный вес имеет вершина 4. Приписываем ей постоянный вес         = 6.

Положим i = 4.

Шаг 3.   Так как i = 4 ≠ t , переходим к шагу 2.

---

Дата добавления: 2019-03-09; просмотров: 256; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!