Нахождение кратчайших путей в графе

Виды задач о кратчайшем пути:

1. Задача о кратчайшем пути в заданный пункт назначения.

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

2.Задача о кратчайшем пути между заданной парой вершин.

Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.

3.Задача о кратчайшем пути между всеми парами вершин.

Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

В различных постановках задачи, роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждого ребра. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).

Алгоритм Дейкстры разработан для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети.

В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер.

Обозначим через u_i кратчайшее расстояние от исходного узла 1 до узла i, через d_ij - длину ребра (i, j). Тогда для узла j определим метку [u_j, i] следующим образом:

[u_j, i] = [u_i + d_ij, i], d_ij >= 0

Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный

Вычислительная схема алгоритма состоит из следующих шагов.

Шаг 0. Исходному узлу (узел 1) присваивается метка [0, -]. Полагаем i = 1.

Шаг i. а) Вычисляются временные метки [u_i + d_ij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [u_j, k], полученную от другого узла k, и если u_i + d_ij < u_j, тогда метка [uj, k] заменяется на [u_i + d_ij, i].

b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [u_r, s] с наименьшим значением расстояния ur среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r повторяем шаг i.

Таблица для "Шаг 1"
Узел	Метка	Статус метки
	[0, -]	Постоянная
	[0 + 100, 1] = [100, 1]	Временная
	[0 + 30, 1] = [30, 1] <-	Временная

В результате выполнения алгоритма на каждом шаге получаем таблицу меток, состоящую из столбцов " Узел", "Метка", " Статус метки".

Таблица для "Шаг 2"
Узел	Метка	Статус метки
	[0, -]	Постоянная
	[100, 1]	Временная
	[30, 1] <-	Временная
	[30 + 10, 3] = [40, 3] <-	Временная
	[30 + 60, 3] = [90, 3]	Временная

Алгоритм позволяет проводить вычисления непосредственно по схеме сети, как показано на рисунке.

Пример. На рисунке показана транспортная сеть, состоящая из пяти городов (расстояния между городами в километрах)

Шаг 0. Назначаем узлу 1 постоянную метку [0,-].

Шаг 1. Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток:

Среди узлов 2 и 3 узел 3 имеет наименьшее значение расстояния (u₃ = 30). Поэтому статус метки этого узла изменяется на "постоянная".

Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов:

Таблица для "Шаг 3"
Узел	Метка	Статус метки
	[0, -]	Постоянная
	[40 + 15, 4] = [55, 4] <-	Временная
	[30, 1]	Постоянная
	[40, 3]	Постоянная
	[90, 3] или [40 + 50, 4] = [90, 4]	Временная

Временный статус метки [40, 3] узла 4 заменяется на постоянный (u4 = 40).

Шаг 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список:

Временная метка [100, 1], полученная узлом 2 на втором шаге, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем шаге узел 5 получает две метки с одинаковым значением расстояния u5 = 90.

Шаг 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном шаге получаем такой же список меток, как и на предыдущем шаге, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остается только узел 5, но так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается.

Алгоритм позволяет проводить вычисления непосредственно по схеме сети, как показано на рисунке. В скобках указан номер шага.

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

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1).

Таким образом, получаем путь 1->3->4->2 общей длиной 55 километров.

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

Например, для определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов:

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1).

⇐ Предыдущая1234

Поделиться:

Воспользуйтесь поиском по сайту: