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

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

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

Если вы хотите найти ответить на вопросы, чем этот алгоритм лучше 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] Решения авторские.

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;
}

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

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

Первый шаг

Второй шаг

Третий шаг

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

Четвертый шаг

Пятый шаг

Шестой шаг

Реализация алгоритма Дейкстры

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

Реализация на C++

Результат выполнения

Назад: Алгоритмизация

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

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

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

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

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

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

Для определения самого
кратчайшего пути (то есть последовательности
вершин) необходимо ввести еще один
массив P вершин, где
P[v]
содержит вершину, непосредственно
предшествующую вершине v
в кратчайшем пути.

Алгоритм:

procedure
Dijkstra;

begin

S
:= источник;

for
i := 2 to n do begin

D[i]
:= C[источник, i];

P[i]
:= источник;

end;

for
i := 1 to n-1 do begin

выбор
из множества VS такой вершины w,

что
значение D[w] минимально;

добавить
w к множеству S;

for
каждая вершина v из множества VS do begin

D[v]
:= min(D[v], D[w] + C[w, v]);

if
D[w] + C[w, v]< D[v] then P[v] := w;

end;

end;

end

Рисунок 53. Алгоритм Дейкстры

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

Время выполнения этого
алгоритма, если для представления графа
используется матрица смежности, имеет
порядок O(n²),
где n – количество
вершин графа.

1. Алгоритм Флойда

Этот алгоритм решает
задачу нахождения кратчайших путей
между всеми парами вершин графа. Более
строгая формулировка этой задачи
следующая: есть ориентированный граф
G = (V, Е),
каждой дуге (v, w)
этого графа сопоставлена неотрицательная
стоимость C[v, w].
Общая задача нахождения кратчайших
путей заключается в нахождении для
каждой упорядоченной пары вершин (v, w)
любого пути от вершины v
в вершину w, длина
которого минимальна среди всех возможных
путей от v к w.

Можно решить эту
задачу, последовательно применяя
алгоритм Дейкстры для
каждой вершины, объявляемой в качестве
источника. Но существует прямой способ
решения данной задачи, использующий
алгоритм Флойда. Для
определенности положим, что вершины
графа последовательно пронумерованы
от 1 до n. Алгоритм
Флойда использует матрицу
A размера
nn,
в которой вычисляются длины кратчайших
путей. В начале
A[i, j] = C[i, j]
для всех i <> j.
Если дуга (i, j)
отсутствует, то C[i, j] = .
Каждый диагональный элемент матрицы A
равен 0.

Над матрицей A
выполняется n итераций.
После k-й
итерации A[i, j]
содержит значение наименьшей длины
путей из вершины i в
вершину j, которые не
проходят через вершины с номером, большим
k. Другими словами,
между концевыми вершинами пути i
и j могут находиться
только вершины, номера которых меньше
или равны k.

На k-й
итерации для вычисления матрицы A
применяется следующая формула:
А_k[i, j] = min(A_k-1[i, j], A_k-1[i, k]
+ A_k-1[k, j]).

Нижний индекс k
обозначает значение матрицы А
после k-й
итерации, но это не означает, что
существует n различных
матриц, этот индекс используется для
сокращения записи.

Равенства
A_k[i, k] = A_k-1[i, k]
и A_k[k, j] = A_k-1[k, j]
означают, что на k-й
итерации элементы матрицы A,
стоящие в k-й
строке и k-м столбце,
не изменяются. Более того, все вычисления
можно выполнить с применением только
одного экземпляра матрицы A.
Представим алгоритм Флойда
в виде следующей процедуры.

procedure
Floyd (var A: array[1..n, 1..n] of real;

С:
аrrау[1..n, 1..n] of real);

var

i,
j, k: integer;

begin

for
i := 1 to n do

for
j := 1 to n do A[i, j] := C[i, j];

for
i := 1 to n do A[i, i] := 0;

for
k := 1 to n do

for
i := 1 to n do

for
j : = 1 to n do

if
(A[i, k] + A[k, j]) < A[i, j] then

A[i,
j] := A[i, k] + A[k, j];

end;

Рисунок 54. Алгоритм Флойда

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

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

Время выполнения этого
алгоритма, очевидно, имеет порядок
O(n³),
поскольку в нем присутствуют вложенные
друг в друга три цикла.

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

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