Задача о нахождении кратчайших путей в графе и методы ее решения.

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения.

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

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).

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

 

Практические задания

1. Решите задачи «о переправах», изобразите решение гра­фом.

1. Три генерала - Строгий, Лихой и Грозный - со своими адъютантами переправлялись через реку с помощью двухместной лодки. Адъютант может либо перевозить своего генерала, либо пе­реправляться с другим адъютантом. Однако ни один из генералов не разрешил своему адъютанту ни оставаться с другим генералом вдвоем на берегу, ни переправляться с ним через реку. Как они переправились через реку?

2. Трое мужчин и три женщины должны переправиться через реку. У них была одна лодка, которая вмещала только двух чело­век. Грести умели все мужчины и только одна женщина. Кроме того, женщины требовали, чтобы ни на одном берегу не остава­лось больше женщин, чем мужчин. Как им переправиться через реку?

3. Муж, жена и двое детей должны переправиться на противо­положный берег реки при помощи лодки. Муж и жена весят по 100 кг, а дети - по 50. Как им быть, если лодка вмещает до 100 кг и каждый из них умеет грести?

4. Человеку необходимо было переправить через реку с помо­щью лодки волка, козу и капусту. В лодке мог поместиться только человек, а с ним или волк, или коза, или капуста. Но если оста­вить волка с козой без человека, то волк съест козу, если оставить козу с капустой, то она съест капусту, а в присутствии человека никто никого не ел. Человек все-таки перевез через реку и волка, и козу, и капусту. Как он это сделал?

2. Задачи на поиск «фальшивой монеты» решите с помощью графов.

1. Из 9 монет одна фальшивая (более легкая). Как двумя взве­шиваниями на чашечных весах определить фальшивую монету?

2. Из 80 одинаковых по виду монет одна более легкая (фальши­вая). Как четырьмя взвешиваниями на чашечных весах определить фальшивую?

3. Из 28 монет одна более легкая. Как при помощи 4 взвешива­ний определить ее?

4. Из 27 монет одна более легкая. Как при помощи 3 взвешива­ний определить ее?

5. Из 81 монеты одна более легкая. Показать, что 4 взвешива­ний достаточно, чтобы ее определить.

6. Из 82 монет одна более легкая. Какое наименьшее число взве­шиваний необходимо для определения этой монеты?

7. Из т одинаковых по виду монет одна фальшивая (более лег­кая). Указать наименьшее число взвешиваний, необходимых для определения фальшивой монеты.

5. Задача о максимальном потоке и алгоритм Форда-Фалкертона.