Задача о кратчайшем пути на графе. Алгоритм Дейкстры


Download 80.42 Kb.
bet1/4
Sana27.12.2019
Hajmi80.42 Kb.
TuriЗадача
  1   2   3   4

§7. Задача о кратчайшем пути на графе. Алгоритм Дейкстры

Напомним, что сетью называется пара N=(G,α), где G – орграф, а α – функция из множества вершин графа в множество действительных чисел. Другими словами, каждой дуге графа поставлено в соответствие некоторое неотрицательное число, которое в данном случае называется длиной дуги. Введем длину пути как сумму длин дуг, составляющих путь. Расстоянием d(u,v) от вершины u до вершины v называется длина кратчайшего пути из u в v. Если нет ни одного пути из u в v, то считают d(u,v)=∞. Расстояние от u до u равно нулю.

Для сети N возникает задача нахождения расстояния d(u,v) для данных вершин u и v и соответствующего кратчайшего пути. Известно несколько способов решения этой задачи. Мы рассмотрим один из них, основой которого является алгоритм Дейкстры. Он вычисляет расстояние от фиксированной вершины v0 до всех остальных вершин сети.

Прежде, чем привести описание алгоритма, введем необходимые обозначения. Пусть N=(G,α) – сеть, v0 – фиксированная вершина этой сети, v1,…,vm – остальные вершины. На множестве пар вершин (u,v) введем функцию L(u,v) следующим образом:



L(u,v)=

α(e), если e – дуга с началом в u и концом в v,

∞ – если такой дуги не существует.

В описании алгоритма участвует еще некоторое подмножество S множества V вершин графа. В ходе выполнения алгоритма вершины последовательно исключают из S, до тех пор, пока не останется ни одной, и вычисляют величины d(vi), равные кратчайшему пути из v0 в vi , не содержащему вершин из S. Алгоритм также имеет графическую реализацию, в которой множеству S соответствуют неокрашенные вершины, а окрашивание – это исключение вершины из S. Итак, дадим формальное описание алгоритма Дейкстры.

Шаг 1. (инициализация). Положить S:=V\{v0} (то есть окрасить вершину v0), d(vi)=∞ для всех i=1,…,m, положить y= v0.

Шаг 2. Для всех vS (т.е. для всех неокрашенных вершин) пересчитать d(v) по формуле: d(v) =min{ d(v), d(y)+L(y,v)} . Если все d(v)= ∞, перейти к шагу 5 (это означает, что в графе отсутствуют пути из v0 в неокрашенные вершины).

Шаг 3. Выбрать в S вершину w, для которой величина d(v) минимальна, и положить S:=S\{w}, т.е. окрасить вершину w. Окрасить дугу, ведущую в вершину w из вершины, которая была взята в качестве y последний раз, когда в менялось значение d для вершины w . Положить y= w. Если S не пусто, перейти к шагу 2, иначе к шагу 4.

Шаг 4. Конец работы алгоритма.

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



Пример 1. Для графа, изображенного на рис. 37найти расстояния от вершины v0 до остальных вершин и построить дерево кратчайших путей с корнем в v0 .

Рис. 37.


Работа алгоритма будет иллюстрироваться заполнением приведенной ниже таблицы. Кроме того, для каждой строки таблицы приводится рисунок, соответствующий графической реализации алгоритма; на этом рисунке окрашенные вершины изображаются черным кружком, окрашенные ребра выделены жирными линиями.



y

d(v1)

d(v2)

d(v3)

d(v4)

d(v5)

Рисунок

0

v0











Рис.38

1

v0

4

1







Рис.39

2

v2

3






5



Рис.40

3

v1







4

5

8

Рис.41

4

v3










5

8

Рис.42

5

v4













8

Рис.43

Download 80.42 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling