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

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

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

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. Задача о максимальном потоке и алгоритм Форда-Фалкертона.