Задача построения кратчайшего пути из заданной вершины

 

Пусть – конечный связный орграф. Пусть в графе G каждой дуге (i, j) поставлено в соответствие некоторое неотрицательное число ℓ _ij, которое здесь назовем длиной ( весом) дуги. В этом случае орграф называется взвешенным графом или сетью.

Постановка задачи. Задана сеть, , в которой выделены две вершины s и t. Найти путь минимальной длины из заданной вершины s в заданную вершину t.

Для каждой вершины i Î I определим множество вершин, соседних справа:

,

т.е. это те вершины, которые достижимы из вершины i посредством одной дуги.

Предлагаемый ниже алгоритм основан на упорядочении вершин сети по возрастанию расстояния от вершины s. Через ℓ (s, i) обозначим минимальное расстояние от вершины s до вершины i.

Поиск 1-ой ближайшей вершины i₁ к вершине s.

1) Определим множество (множество вершин соседних справа для вершины s).

2) Определим вершину i₁ из условия:

.

Другими словами, среди вершин, удовлетворяющих условию 1), найдем самую близкую к вершине s. Таким образом, ℓ (s, i₁) =.

Поиск 2-ой ближайшей вершины i₂ к вершине s (см. рис. 6.1).

1) Среди вершин множества I \{s, i₁} определяем вершину, ближайшую к вершине i₁. Для этого

- определим множество \{s},

-

определим вершину, для которой

2) Среди вершин множества \{i₁} определяем вершину, ближайшую к вершине s: .

3) Определим вершину i₂:

если + ³ , то i₂ = и;

если + < , то i₂ = и.

Далее находим 3-ю и т.д. ближайшие вершины к вершине s.

Пусть определены m-1 ближайших вершин к вершине s:

,

и для них вычислены минимальные расстояния, .

Поиск m-ой ближайшей вершины i_m к вершине s.

1) Для каждой из вершин i_p, , определим множество вершин, соседних справа, и исключим из каждого из них вершины s, i₁, i₂, i₃, …, i_m-1 (если они попали в них):

= \{s, i₁, i₂, i₃, …, i_m-1}.

Затем определим вершины, , для которых

(p(, .

2) Среди вершин множества определяем вершину, ближайшую к вершине s:

.

3) Среди вершин определим вершину i_m по правилу:

=.

Поскольку заданная сеть является конечной, то количество элементов множеств вида и на некотором шаге начнет убывать. Если путь из вершины s в вершину t существует, то через конечное число шагов определим и число. Если же путь из вершины s в вершину t не существует, то на каком-то шаге указанные выше множества станут пустыми (вершины не будут иметь соседних справа среди остальных вершин сети).

Изложенная идея упорядочения вершин по их расстоянию от вершины s лежит в основе алгоритма Дейкстры. В ходе его выполнения всем вершинам сети присваиваются метки – временные или постоянные. Временная метка – это число, дающее верхнюю оценку минимального пути из вершины s в рассматриваемую вершину. Постоянная метка – число, равное длине минимального пути.

 

Алгоритм Дейкстры

Шаг 0. Каждой вершине i сети G ставим в соответствие метку:

 

– постоянная метка, остальные метки временные.

Шаг k. Определены вершины с постоянными метками: , и p – последняя вершина, получившая постоянную метку.

1 этап (этап обновления меток).

1) Находим – множество вершин, соседних справа для вершины р.

2) Находим: из множества исключаем вершины, имеющие постоянные метки, т.е. = \.

3) Для каждой вершины i Î пересчитываем метки по правилу:

=,

где – прежняя временная метка вершины i, – новая временная метка вершины i, – постоянная метка вершины р, – длина дуги.

2 этап (перевод одной из временных меток в постоянную метку).

1) Формируем множество I_k – множество вершин с временными метками.

2) Находим вершину с минимальной временной меткой:

=. (6.1)

3) Метка – становится постоянной, вершина.

Выход из алгоритма (принцип останова).

Если, то – минимальная длина пути из заданной вершины s в заданную вершину t.

Если = Æ и вершина t имеет временную метку, равную ¥, то в сети не существует пути из вершины s в вершину t.

Замечание 1. Алгоритм может быть модифицирован таким образом, что кроме значения минимального пути будет получен и сам путь, например, в виде последовательности вершин. Для этого метку вершины на шаге обновления меток дополним информацией о вершине, через которую пересчитывается минимум в (6.1), т.е. метка вершины будет состоять из двух частей. Как только вершина t получит постоянную метку, по второй части метки определим предшествующую ей вершину. По второй части метки последней определим ей предшествующую вершину и т.д., пока не доберемся до вершины s.

Замечание 2. Алгоритм может быть использован для решения задачи о кратчайшем пути из заданной вершины до любой другой вершины. В этом случае изменяется принцип останова.

Если все вершины получили постоянные метки, то любая вершина достижима из вершины s. Значение постоянной метки вершины есть длина минимального пути из заданной вершины s в эту вершину.

Если на некотором шаге ⁺(p) = Æ и некоторые вершины имеют временную метку, равную ¥, то в сети не существует пути из вершины s до этих вершин.

Пример. На сети, представленной на рис. 6.1, найти кратчайший путь из вершины s до вершины t.

 

Итерация 0. ℓ (s) = 0, ℓ (i) = ¥, iÎ {1, 2, 3, 4, 5, t}, p = s.

Дальнейшие вычисления на каждой итерации оформим в виде таблиц.

Итерация 1.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
s	1, 2, 3		ℓ ’(1) = min{¥; 0+7}=7, ℓ ’(2) = min{¥; 0+1}=1, ℓ ’(3) = min{¥; 0+3}=3.	s s s	(min)	врем. пост.врем.

 

Итерация 2.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
	4, 5		ℓ ’(4) = min{¥; 1+2}=3, ℓ ’(5) = min{¥; 1+4}=5.		(min)	врем. врем.
другие вершины с временными метками
			ℓ ’(1) = 7, ℓ ’(3) = 3.	s s	(min)	врем. пост.

 

Замечание. Выбор вершины р неоднозначен, можно выбрать либо вершину 4, либо вершину 3. Полагаем р = 3.

 

Итерация 3.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
			ℓ ’ (5) = min{5; 3+4}=5.			врем.
другие вершины с временными метками
			ℓ ’(1) = 7, ℓ ’(4) = 3.	s	(min)	врем. пост.

 

Итерация 4.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
	t	t	ℓ ’(t) = min{¥; 3+3}=6.			врем.
другие вершины с временными метками
			ℓ ’(1) = 7, ℓ ’(5) = 5.	s	(min)	врем. пост.

 

Итерация 5.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
	4, t	t	ℓ ’(t) = min{6; 5+3}=6		(min)	пост.
другие вершины с временными метками
			ℓ ’(1) = 7	s		врем.

 

Так как вершина t получила постоянную метку, то решение закончено. Длина кратчайшего пути из заданной вершины s в вершину t равна 6. По второй части метки вершин восстанавливаем этот путь: t 4 2 s.

Замечание 3. Алгоритм неприменим к сетям, где есть отрицательные веса дуг. На рис. 6.2 представлена сеть, где ℓ _1t = –2. Согласно алгоритму Дейкстры минимальный путь из вершины s в вершину t равен 3 (вершина t является 1-ой ближайшей). На самом деле минимальный путь проходит через вершину 1, его длина равна 2.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: