Как найти минимальный путь в орграфе

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

Пусть G={S,U,Ω}
– ориентированный граф со взвешенными
дугами. Обозначим s –
вершину – начало пути и t
– вершину конец пути. Веса дуг должны
быть положительными.

Этап
1.
Нахождение
длины кратчайшего пути.

Шаг 1.
Присвоение вершинам
начальных меток.

Полагаем

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

полагаем
d(x)
= ∞ и считаем эти метки временными. Пусть

обозначение
текущей вершины.

Шаг 2.
Изменение меток.

Для каждой вершины x_i
с временной меткой, непосредственно
следует за вершиной

,
меняет её метку в соответствии со
следующим правилом:

(1)

Шаг
3.
Превращение
метки
из
временной
в
постоянную.

Из всех вершин с временными метками
выбираем вершину

с наименьшим значением метки:

(2)

Превращаем
эту метку в постоянную и полагаем

.

Шаг 4.
Проверка на
завершение первого
этапа.

Если

—
длина кратчайшего пути от S
до t. В противном случае
происходит возвращение ко второму шагу.

Этап 2.
Построение кратчайшего
пути.

Шаг
5.
Последовательный
поиск
дуг
кратчайшего
пути.

Среди вершин, непосредственно
предшествующих вершине

с постоянными метками, находим вершину
х_i,
удовлетворяющую соотношению

.
(3)

Включаем дугу

в
искомый путь и полагаем

.

Шаг
6.
Проверка
на
завершение
второго
этапа.

Если

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

Пример. Задана весовая
матрица Ω сети G:

Рис.
34

Найти
минимальный путь из вершины х₁
в вершину х₆ по алгоритму
Дейкстры.

Решение. Т.к. в данном
графе есть цикл между вершинами х₂,
х₃ и х₅, то
вершины графа нельзя упорядочить по
алгоритму Фалкерсона.

Этап 1.

Шаг 1.
Полагаем

.

Первая итерация.

Шаг 2.
Множество вершин, непосредственно
следующих за

с
временными метками

.
Пересчитываем временные метки этих
вершин.

Шаг 3.
Одна из временных меток превращается
в постоянную:

Шаг 4.

происходит возвращение на второй шаг.

Вторая итерация.

Шаг 2.

Шаг 3.

Шаг 4.

,
возвращение на 2-ой шаг.

Третья итерация.

Шаг 2.

Шаг 3.

Шаг 4.

возвращение
на 2-ой шаг.

Четвёртая итерация.

Шаг 2.

Шаг 3.

Шаг 4.

возвращение
на 2-ой шаг.

Пятая итерация.

Шаг 2.

Шаг 3.

Шаг 4.

конец
1-го этапа.

Этап 2.

Первая итерация.

Шаг 5.
Составим множество вершин, непосредственно
предшествующих

с постоянными метками

Проверим для
этих двух вершин выполнение равенства
(3):

Включаем дугу
(х₅,х₆) в
кратчайший путь.

.

Шаг 6.

,
возвращение на 5-ый шаг.

Вторая
итерация.

Шаг5.

Включаем дугу (х₁,х₅)
в кратчайший путь.

.

Шаг 6.

,
завершение второго этапа.

Итак
кратчайший путь от вершины х₁
до вершины х₆
построен. Его длина (вес) равен 15, сам
путь образует следующая последовательность
дуг:

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Определение. Назовём орграф  нагруженным, если на множестве дуг  определена некоторая функция  , которую часто называют весовой функцией.

Тем самым в нагруженном орграфе  каждой дуге поставлено в соответствие некоторое дей­ствительное число . Значение  будем называть длиной дуги .

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

Определение. Путь в нагруженном орграфе  из вершины  в вершину , где , называется минимальным, если он имеет минималь­ную длину среди всех путей орграфа  из  в . Аналогично определяется и минимальный маршрут в нагруженном графе .

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

Пусть  — нагруженный орграф, , . Введем величины , где , …, , , ,… Для каждых фиксированных  и  величина  равна длине минималь­ного пути среди путей из  в , содержащих не более  дуг; если же таких путей нет, то =. Кроме того, если произ­вольную вершину считать путем из ₁ в _i нулевой длины, то величины  можно ввести также и для , при этом

 (1)

Введем также в рассмотрение квадратную матрицу  порядка  с элементами

которую будем называть матрицей длин дуг нагруженного орграфа.

Следующее утверждение дает простые формулы для вычисле­ния величин .

Утверждение.  

  .

Используя данное утверждение, нетрудно описать алгоритм нахождения таблицы значений величин  (будем записывать её в виде матрицы, где — номер строки,  — номер столбца). Действительно, используя рекуррентные соотношения (2), (3) и исходя  из (1), последовательно определяем набор величин  (()-й столбец матрицы), начиная с , а затем шаг за шагом увеличиваем значение  до любой необходимой величины.

Алгоритм Форда – Беллмана нахождения минимального пути

в нагруженном орграфе  из  в  

Шаг 1. Пусть мы уже составили таблицу величин . Если  не достижима из  (предполагаем, что все величины  конечны). В этом случае работа алгоритма заканчивается.

Шаг 2. Пусть . Тогда число  выражает длинны любого минимального пути из  в в нагруженном орграфе . Определим минимальное число , при котором выполняется равенство . По определению чисел  получим, что  — минимальное число дуг в пути среди всех минимальных путей из  в  в нагруженном орграфе .

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

. . . . . .                                   (4)

Из (4) с учётом того, что , имеем , откуда, используя (1), получаем

 (5)

Складывая равенства (4) и учитывая (5), имеем

т.е. — искомый минимальный путь из  в в нагруженном орграфе . Заметим, что в этом пути ровно  дуг Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из  в  в нагруженном оргра­фе .

Замечание. Номера , удовлетворяющие (4) вообще говоря, могут быть выделены неоднозначно. Эта неодно­значность соответствует случаям, когда существует несколько различных путей из   в  с минимальным числом дуг среди минимальных путей из  в  в нагруженном орграфе .

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

Пример 83.

Определить минимальный путь из v₁ в v₆ в нагруженном орграфе D, изображенном на рис. 3.17.

Рис. 3.17. Нагруженный орграф для примера 83

Решение.

Составим матрицу C(D) длин дуг нагруженного орграфа D (табл. 3.3). Справа от матрицы C(D) припишем шесть столбцов, которые будем определять, используя  рекуррентное соотношение (2) и исходя из (1).

Величина  выражает длину минимального пути из v₁ в v₆ в нагруженном орграфе D. Найдем минимальное число , при котором выполняется равенство . Получаем, что k₁ = 4. Таким образом, минимальное число дуг в пути среди всех минимальных путей из v₁ в v₆ в нагруженном графе D равняется 4.

Определим теперь последовательность номеров i₁, i₂, i₃, i₄, i₅, где i₁ = 6, удовлетворяющих (4) (для этого используем формулу (2)).

Таблица 3.3 Матрица длин дуг нагруженного орграфа

	v1	v2	v3	v4	v5	v6
v1			5	5	2	12		0	0	0	0	0	0
v2						2				7	5	5	5
v3		2							5	3	3	3	3
v4		2							5	4	4	4	4
v5			1	2					2	2	2	2	2
v6									12	12	9	7	7

Получаем, что в качестве такой последовательности надо взять номера 6, 2, 3, 5, 1, так как

Тогда v₁v₅v₃v₂v₆ – искомый минимальный путь из v₁ в v₆ в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из v₁ в v₆ .

vector<int> bfs(int s) {
    // длина любого кратчайшего пути не превосходит n - 1,
    // поэтому n - достаточное значение для "бесконечности";
    // после работы алгоритма dist[v] = n, если v недостижима из s
    vector<int> dist(n, n);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return dist;
}

// теперь bfs принимает 2 вершины, между которыми ищется пути
// bfs возвращает кратчайший путь из s в t, или же пустой vector, если пути нет
vector<int> bfs(int s, int t) {
    vector<int> dist(n, n);
    vector<int> p(n, -1);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                p[u] = v;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    
    // если пути не существует, возвращаем пустой vector
    if (dist[t] == n) {
        return {};
    }

    vector<int> path;
    while (t != -1) {
        path.push_back(t);
        t = p[t];
    }
    
    // путь был рассмотрен в обратном порядке, поэтому его нужно перевернуть
    reverse(path.begin(), path.end());
    return path;
}

// INF - infinity - бесконечность
const long long INF = (long long) 1e18 + 1;

vector<long long> dijkstra(int s) {
    vector<long long> dist(n, INF);
    dist[s] = 0;
    vector<bool> used(n);
    
    while (true) {
        // находим вершину, из которой будем релаксировать
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && (v == -1 || dist[i] < dist[v])) {
                v = i;
            }
        }
        
        // если не нашли подходящую вершину, прекращаем работу алгоритма
        if (v == -1) {
            break;
        }
        
        for (auto &e : adj[v]) {
            int u = e.first;
            int len = e.second;
            if (dist[u] > dist[v] + len) {
                dist[u] = dist[v] + len;
            }
        }
    }
    
    return dist;
}

Алгоритм Дейкстры. Разбор Задач

Поиск оптимального пути в графе. Такая задача встречается довольно часто и в повседневной жизни, и в мире технологий. Справиться с такими вызовами помогает подход, который должен быть в арсенале каждого программиста — алгоритм Дейкстры.

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

Введение

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

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

Условие неотрицательности весов рёбер крайне важно и от него нельзя просто избавиться. Не получится свести задачу к решаемой алгоритмом Дейкстры, прибавив наибольший по модулю вес ко всем рёбрам. Это может изменить оптимальный маршрут. На рисунке видно, что в первом случае оптимальный путь между и (сумма рёбер на пути наименьшая) изменяется при такой манипуляции. В оригинале путь проходит через , а после добавления семёрки ко всем рёбрам, оптимальный путь проходит через

Как ведёт себя алгоритм Дейкстры на исходном графе, мы разберём, когда выпишем алгоритм. Но для начала зададимся другим вопросом: «почему не применить поиск в ширину для нашего графа?». Известно, что метод BFS находит оптимальный путь от произвольной вершины в ориентированном графе до любой другой вершины, но это справедливо только для рёбер с единичным весом.

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

Чтобы этого избежать предлагается использовать алгоритм Дейкстры. Опишем его:

Инициализация:

Основный цикл алгоритма:

• Пока все вершины не исследованы (или формально ), повторяем:

В итоге исполнения этого алгоритма, массив будет содержать все оптимальные пути, исходящие из .

Примеры работы

Рассмотрим граф выше, в нём будем искать пути от до всего остального.

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

Теперь рассмотрим граф с отрицательными весами, упомянутый выше. Напомню, алгоритм Дейкстры на таком графе может работать некорректно.

Первым шагом отбирается ребро вдоль синей стрелки, поскольку это ребро наименьшего веса из исходной вершины. Затем выбирается ребро Это зафиксирует навсегда неверный путь от к , в то время как оптимальный путь проходит через центр с отрицательным весом. Последним шагом, будет добавлена вершина .

Оценка сложности алгоритма

К этому моменту мы разобрали сам алгоритм, ограничения, накладываемые на его работу и ряд примеров его применения. Давайте упомянем какова вычислительная сложность этого алгоритма, поскольку это пригодится нам для решения задач, ради которых затевалась эта статья.
Базовый подход, основанный на циклах, предполагает проход по всем рёбрам каждого узла, что приводит к сложности .

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

Что еще можно сказать о куче:

• это сбалансированное бинарное дерево,
• ключ текущего узла всегда меньше, либо равен ключей дочерних узлов.

Интересную задачу с использованием куч я разбирал ранее в этом посте.

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

Далее перейдём к разбору задач!

Задача №1

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

Решение

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

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

В отличии от классического алгоритма, решение этой задачи должно поддерживать величину актуального узкого места пути, приводящего в вершину . А при добавлении новой вершины из , мы должны смотреть не увеличивает ли ребро величину узкого места пути, которое теперь приводит в .
Если ребро увеличивает узкое место, то лучше рассмотреть вершину , ребро до которой легче . Поиск неувеличивающих узкое место ребёр нужно осуществлять не только среди соседей определенного узла , но и среди всех , поскольку отдавая предпочтение вершине, путь в которую имеет наименьшее узкое место в данный момент, мы гарантируем, что мы не ухудшаем ситуацию для других вершин.

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

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

Стоит пояснить, что поиск по осуществляется, только для существующих связей а это вес ребра .

Задача №2

Предлагается решить более практическую задачу. Пусть городов, между ними существуют пути, заданные массивом edges[i] = [city_a, city_b, distance_ab], а также дано целое число mileage.

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

Стоит отметить, что граф неориентированый, т.е. по пути между городами можно двигаться в обе стороны, а длина пути между городами a и c может быть получена как сумма длин путей a -> b и b -> c, если есть маршрут a -> b -> c

Решение

С решением данной проблемы нам поможет алгоритм Дейкстры и описанная выше реализация с помощью кучи. Поставщиком этой структуры данных станет библиотека heapq в Python.

Будем использовать алгоритм Дейкстры для того, чтобы подсчитать количество соседних городов, расстояние до которых меньше mileage, для каждого из городов. Соберем количества соседей в в одном месте и найдем минимум из них.

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

Давайте опишем функцию решения:

def least_reachable_city(n, edges, mileage):
        """
        входные параметры:
            n --- количество городов,
            edges --- тройки (a, b, distance_ab),
            mileage --- максимально допустимое расстояние между городами 
            для соседства
        """
        # заполняем список смежности (adjacency list), в нашем случае это 
        # словарь, в котором ключи это города, а значения --- пары 
        # (<другой_город>, <расстояние_до_него>)

        graph = {}
        for u, v, w in edges:
            if graph.get(u, None) is None:
                graph[u] = [(v, w)]
            else:
                graph[u].append((v, w))
            if graph.get(v, None) is None:
                graph[v] = [(u, w)]
            else:
                graph[v].append((u, w))
        
        # локально объявим функцию, которая будет считать кратчайшие пути в 
        # графе от вершины, до всех вершин, удовлетворяющих условию
        def num_reachable_neighbors(city):
            # создаем кучу, из одного элемента с парой, задающей нулевую 
            # длину пути до самого исходного города
            heap = [(0, city)]
            # и массив, содержащий города и кратчайшие 
            # расстояния до них от исходного
            distances = {}
            # затем, пока куча не пуста, извлекаем ближайший 
            # от посещенных городов город
            while heap:
                currDist, neighb = heapq.heappop(heap)
                # если кратчайшее ребро ведет к городу, где мы уже знаем 
                # оптимальный маршрут, то завершаем итерацию
                if neighb in distances:
                    continue
                # в остальных случаях, и если сосед не является отправным 
                # городом, мы добавляем новую запись в массив кратчайших расстояний
                if neighb != city:    
                    distances[neighb] = currDist
                # обрабатываем всех смежных городов с соседом, добавляя их в кучу 
                # но только если: а) до них еще не известен кратчайший маршрут и б) путь до них через neighb не выходит за пределы mileage
                for node, d in graph[neighb]:
                    if node in distances:
                        continue
                    if currDist + d <= mileage:
                        heapq.heappush(heap, (currDist + d, node))
            # возвращаем количество городов, прошедших проверку
            return len(distances)
        
        # выполним поиск соседей для каждого из городов
        cities_neighbors = {num_reachable_neighbors(city): city for city in range(n)}
        # вернём номер города, у которого наименьшее число соседей
        # в пределах досигаемости
        return cities_neighbors[min(cities_neighbors)]

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

Заключение

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

Стоит еще раз отметить, что алгоритм не работает, когда в графе существуют отрицательные веса. Для этого существует подход динамического программирования — алгоритм Беллмана – Форда, что может послужить темой другой статьи. Несмотря на это, алгоритм Дейкстры является представителем идеального баланса простоты и мощи, для решения прикладных задач.

Статья подготовлена в преддверии старта курса «Алгоритмы для разработчиков». Узнать о курсе подробнее, а также зарегистрироваться на бесплатный демоурок можно по ссылке.

Информация

[1] Условия задач взяты из книги «Algorithms Illuminated: Part 2: Graph Algorithms and Data Structures» от Tim Roughgarden,
[2] и с сайта leetcode.com.
[3] Решения авторские.