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

Известна схема дорог. Требуется перевезти груз из одного пункта в другой по маршруту минимальной длины.

Двигаясь от конечного пункта к начальному пункту, каждой вершине припишем число по определенным правилам. Конечной вершине присвоим число 0. Если i-я вершина в направлении от начального пункта к конечному пункту непосредственно соединена с вершинами j₁, …, j_k, которым приписаны числа r(j₁), …, r(j_k), то вершине i приписывается число , где – длина ребра.

Пусть этот минимум достигается для вершины j_m. Тогда ребро (i, j_m) отмечаем жирной стрелкой от i к j_m. Если таких j_m несколько, то на этом шаге будет несколько выделенных ребер.

Число, приписанное начальному пункту, равно минимальной длине искомого маршрута. Для получения оптимального маршрута двигаются по выделенным стрелкам от начального пункта к конечному.

Пример. Найти маршрут минимальной длины от пункта 1 к пункту 11.

Длина кратчайшего пути равна …. Двигаясь от начальной вершины к конечной по выделенным ребрам, получим кратчайший путь .

3. Задача определения максимального потока

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

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

Мощность потока может зависеть от его направления.

Это условное обозначение означает, что мощность потока от узла 1 к узлу 2 равна 6, а мощность потока от узла 2 к узлу 1 равна 0, т.е. это «улица с односторонним движением».

Условное обозначение

означает, что мощность потока в каждом направлении равна 2.

Алгоритм:

Полагаем искомую величину максимального потока равной нулю.

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

Шаг 2. Найти наименьшее значение мощности дуги P_f на выбранном пути шага 1. Увеличить поток через сеть на величину P_f.

Шаг 3. На пути из шага 1 сократить на P_f мощности потоков на всех дугах в направлении потока и увеличить на P_f мощности потоков на всех дугах, в обратном направлении. Перейти к шагу 1.

Пример. Система автодорог «Север-Юг», проходящих через Псковскую область, может обеспечить пропускные способности, показанные на схеме (тыс. автомашин в час).

Определить максимальный поток через эту систему (тыс. автомашин в час).

Искомую величину максимального потока положим равной нулю.

Итерация 1. Выберем путь

P_f = min{……..}=…. Поэтому мощности потоков на пути ……… в направлении потока (а именно, … и …) уменьшаем на величину P_f =…, а мощности потоков в обратном направлении на пути ………. (… и …) увеличиваем на P_f =…. Общий поток станет

Получим:

Итерация 2. Выберем путь

P_f = min{………}=…. Все потоки на пути ……… в направлении общего потока (… и …) уменьшаем на P_f =…, а все потоки на этом пути в обратном направлении (… и …) увеличиваем на P_f =…. Общий поток увеличиваем на P_f =… (…………).

Получим:

Итерация 3. Выбираем путь

P_f = min{…………..}=…. Все потоки на пути ……….. в направлении общего потока (………….) уменьшаем на P_f =…, а все потоки на этом пути в обратном направлении (…………) увеличиваем на P_f =…. Общий поток увеличиваем на P_f =… (…………….).

Получим:

Итерация 4. Выбираем путь

P_f = min{………………}=…. Все потоки на пути ……………. в направлении общего потока (……………..) уменьшаем на P_f =…, а все потоки на этом пути в обратном направлении (……………..) увеличиваем на P_f =…. Общий поток увеличиваем на P_f =… (…………..).

Получим:

Итерация 5. Выбираем путь

P_f = min{………………..}=…. Все потоки на пути ……………….. в направлении общего потока (………………..) уменьшаем на P_f =…, а все потоки на этом пути в обратном направлении (………………..) увеличиваем на P_f =…. Общий поток увеличиваем на P_f =… (………….).

Получим:

Больше не существует путей из узла 1 в узел 6 с мощностью, превышающей нуль на всем пути. Следовательно, …. тыс. – это максимальный поток через сеть.

Определим величину и направление потока на каждой дуге. Направление потоков соответствует выбранным путям. Поток проходит по дуге с величиной, равной разнице между первоначальной и конечной мощностями потока:

дуга 1-2: первоначальная мощность равна … (в исходном графе), конечная – … (в последнем графе), следовательно, в направлении от узла 1 к узлу 2 поток имеет мощность

дуга 1-3:

дуга 1-4:

дуга 2-5:

дуга 3-4:

дуга 3-6:

дуга 4-2:

дуга 4-5:

дуга 4-6:

дуга 5-6:

В итоге получим граф, на котором указаны направления и мощности потоков по каждой дуге: