Пример 3.

Лабораторная работа № 13

Тема: Экстремальные задачи на графах (продолжение)

Рассматриваемые вопросы:

- Задача о кратчайшем пути

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

- Задача о максимальном потоке

- Алгоритм Форда-Фалкерсона

1. Задача о кратчайшем пути

Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б?

Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной.

Пример 1.

Рис.1. Исходные данные к задаче о кратчайшем пути

Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.1).

Табл.1. Исходные данные к задаче о кратчайшем пути.

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.1 и в табл.1, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1.

Кроме того, очевидно, что С(1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С(4) = min {С(2) + 4; С(5) + 5}.

Таким образом, проведена реструктуризация задачи - нахождение С(4) сведено к нахождению С(2) и С(5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С(5) = min {С(3) + 2; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому

С(5) = min {3; С(6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому

С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С(4):

С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4.

Задача о кратчайшем пути для конкретных исходных данных (рис.1 и табл.1) полностью решена.

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

Найдем кратчайший путь от вершины x_i до всех вершин, используя алгоритм Дейкстры. Он заключается в том, что вершинам графа присваиваются временные метки, которые затем по определенным правилам заменяются на постоянные метки. Будем использовать обозначения:

L* (x_i) - постоянная метка вершины x_i,

L^н (x_i )- новая временная метка вершины x_i,

L^с (x_i )- старая временная метка вершины x_i,

R_ij - вес ребра, соединяющего вершины x_i и x_j.

Новая временная метка вычисляется по формуле:

L^н (x_i )= min{ L^с (x_i ), R_{ij +} L* (x_i)}

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

Пример 2. Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Построить дерево кратчайших путей.

Рис.2. Исходные данные к задаче о кратчайшем пути

Шаг 1. Начальная вершина x₁, имеет постоянную метку L* (x₁) =0, остальные вершины имеют временную метку ∞.

Шаг 2. Определяем множество последователей вершины Г (x₁)={ x₃ , x₄, x₅, x₂}

Пересчитываем их временные метки по основной формуле. L^н (x₃) =85, L^н(x₄)=75, L^н (x₅ )=57, L^н (x₂) =32.

Берем вершину x₂ с минимальной временной меткой 32, присваиваем этой вершине постоянную метку L* (x₂) = 32.

Шаг 3. Определяем множество последователей вершины Г (x₂)={ x₃, x₅, x₈}. Пересчитываем их временные метки по основной формуле.

L^н (x₃)= min{ 85, 32+70}=85, L^н (x₅ )= min{ 57, 32+23}= 55, L^н (x₈ )= 32+ 64= 96. Берем вершину x₅ с минимальной временной меткой 55, присваиваем этой вершине постоянную метку L* (x₅)= 55.

Шаг 4. Определяем множество последователей вершины Г (x₅)={x₄, x₆, x₇}. Пересчитываем их временные метки по основной формуле.

L^н (x₄ )= min{ 75, 55+10}= 65, L^н (x₆ )= 55+ 11= 66, L^н (x₇ )= 55+20= 75. Берем вершину x₄ с минимальной временной меткой 65, присваиваем этой вершине постоянную метку L* (x₄)=65.

Шаг 5. Определяем множество последователей вершины Г(x₄)={x₃}. Пересчитываем их временные метки по основной формуле. L^н (x₃ )= min{ 85, 65+18}= 83. Берем вершину x₆ с минимальной временной меткой 66, присваиваем этой вершине постоянную метку L*(x₆)=66.

Шаг 6. Определяем множество последователей вершины Г(x₆)={x₄, x₇}. Пересчитываем их временные метки по основной формуле. L^н (x₇ )= min{ 75, 66+7}= 73. Берем вершину x₇ с минимальной временной меткой 73, присваиваем этой вершине постоянную метку L*(x₇)=73.

Шаг 7. Определяем множество последователей вершины Г(x₇)={x₈}. Пересчитываем их временные метки по основной формуле. L^н (x₈ )= min{ 96, 73+12}= 85. Берем вершину x₃ с минимальной временной меткой 83, присваиваем этой вершине постоянную метку L*(x₃)=83.

Шаг 8. Определяем множество последователей вершины Г(x₃)={x₆}. Эта вершина уже имеет постоянную метку. Поэтому берем последнюю вершину x₈ с временной меткой 85, присваиваем этой вершине постоянную метку L*(x₈)=85.

Кратчайшие пути найдены, их длина приведена в последних двух столбцах расчетной таблицы. Построим дерево кратчайших путей (ребра дерева обведены жирным) – ребра (1, 2), (2, 5), (5, 4), (4, 3), (5, 6), (6, 7), (7, 8).

Рис.3. Решение задачи о кратчайшем пути

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

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

Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?

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

Пример 3.

Рис.4. Исходные данные к задаче о максимальном потоке

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.4, можно также задать таблицей (табл.2).

Табл.2. Исходные данные к задаче о максимальном потоке

Решение задачи о максимальном потоке может быть получено из следующих соображений.

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде таблицы (табл.3)

Табл.3. Решение задачи о максимальном потоке