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

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. Dijkstra.

Задача

Дан ориентированный граф $G = (V, E)$, а также вершина $s$.
Найти длину кратчайшего пути от $s$ до каждой из вершин графа. Длина пути — количество рёбер в нём.

BFS

BFS — breadth-first search, или же поиск в ширину.

Этот алгоритм позволяет решать следующую задачу.

Алгоритм работает следующим образом.

1. Создадим массив $dist$ расстояний. Изначально $dist[s] = 0$ (поскольку расстояний от вершины до самой себя равно $0$) и $dist[v] = infty$ для $v neq s$.
2. Создадим очередь $q$. Изначально в $q$ добавим вершину $s$.
3. Пока очередь $q$ непуста, делаем следующее:
   1. Извлекаем вершину $v$ из очереди.
   2. Рассматриваем все рёбра $(v, u) in E$. Для каждого такого ребра пытаемся сделать релаксацию: если $dist[v] + 1 < dist[u]$, то мы делаем присвоение $dist[u] = dist[v] + 1$ и добавляем вершину $u$ в очередь.

Визуализации:

• https://visualgo.net/mn/dfsbfs

• https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/

Интуитивное понимание алгоритма

Можно представить, что мы поджигаем вершину $s$. Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.

Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину – ту непосещенную, которую мы положили в очередь раньше всего.

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

• поиск компонент связности
• проверка графа на двудольность
• построение остова

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

n — количество вершин в графе; adj — список смежности

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

Свойства кратчайших путей

Обозначение: $d(v)$ — длина кратчайшего пути от $s$ до $v$.

Лемма 1.

Пусть $(u, v) in E$, тогда $d(v) leq d(u) + 1$.

Действительно, существует путь из $s$ в $u$ длины $d(u)$, а также есть ребро $(u, v)$, следовательно, существует путь из $s$ в $v$ длины $d(u) + 1$. А значит кратчайший путь из $s$ в $v$ имеет длину не более $d(u) + 1$,

Лемма 2.

Рассмотрим кратчайший путь от $s$ до $v$. Обозначим его как $u_1, u_2, dots u_k$ ($u_1 = s$ и $u_k = v$, а также $k = d(v) + 1$).
Тогда $forall (i < k): d(u_i) + 1 = d(u_{i + 1})$.

Действительно, пусть для какого-то $i < k$ это не так. Тогда, используя лемму 1, имеем: $d(u_i) + 1 > d(u_{i + 1})$. Тогда мы можем заменить первые $i + 1$ вершин пути на вершины из кратчайшего пути из $s$ в $u_{i + 1}$. Полученный путь стал короче, но мы рассматривали кратчайший путь — противоречие.

Корректность

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

1. Расстояния до тех вершин, которые были добавлены в очередь, посчитаны корректно.
2. Вершины лежат в очереди в порядке неубывания расстояния, притом разность между кратчайшими расстояними до вершин в очереди не превосходит $1$.

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

База очевидна.
Переход. Сначала докажем первую часть. Предположим, что $dist[v] + 1 < dist[u]$, но $dist[v] + 1$ — некорректное расстояние до вершины $u$, то есть $dist[v] + 1 neq d(u)$. Тогда по лемме 1: $d(u) < dist[v] + 1$. Рассмотрим предпоследнюю вершину $w$ на кратчайшем пути от $s$ до $u$. Тогда по лемме 2: $d(w) + 1 = d(u)$. Следовательно, $d(w) + 1 < dist[v] + 1$ и $d(w) < dist[v]$. Но тогда по предположению индукции $w$ была извлечена раньше $v$, следовательно, при релаксации из неё в очередь должна была быть добавлена вершина $u$ с уже корректным расстоянием. Противоречие.
Теперь докажем вторую часть. По предположению индукции в очереди лежали некоторые вершины $u_1, u_2, dots u_k$, для которых выполнялось следующее: $dist[u_1] leq dist[u_2] leq dots leq dist[u_k]$ и $dist[u_k] – dist[u_1] leq 1$. Мы извлекли вершину $v = u_1$ и могли добавить в конец очереди какие-то вершины с расстоянием $dist[v] + 1$. Если $k = 1$, то утверждение очевидно. В противном случае имеем $dist[u_k] – dist[u_1] leq 1 leftrightarrow dist[u_k] – dist[v] leq 1 leftrightarrow dist[u_k] leq dist[v] + 1$, то есть упорядоченность сохранилась. Осталось показать, что $(dist[v] + 1) – dist[u_2] leq 1$, но это равносильно $dist[v] leq dist[u_2]$, что, как мы знаем, верно.

Время работы

Из доказанного следует, что каждая достижимая из $s$ вершина будет добавлена в очередь ровно $1$ раз, недостижимые вершины добавлены не будут. Каждое ребро, соединяющее достижимые вершины, будет рассмотрено ровно $2$ раза. Таким образом, алгоритм работает за $O(V+ E)$ времени, при условии, что граф хранится в виде списка смежности.

Неориентированные графы

Если дан неориентированный граф, его можно рассматривать как ориентированный граф с двумя обратными друг другу ориентированными рёбрами.

Восстановление пути

Пусть теперь заданы 2 вершины $s$ и $t$, и необходимо не только найти длину кратчайшего пути из $s$ в $t$, но и восстановить какой-нибудь из кратчайших путей между ними. Всё ещё можно воспользоваться алгоритмом BFS, но необходимо ещё и поддерживать массив предков $p$, в котором для каждой вершины будет храниться предыдущая вершина на кратчайшем пути.

Поддерживать этот массив просто: при релаксации нужно просто запоминать, из какой вершины мы прорелаксировали в данную. Также будем считать, что $p[s] = -1$: у стартовой вершины предок — некоторая несуществующая вершина.

Восстановление пути делается с конца. Мы знаем последнюю вершину пути — это $t$. Далее, мы сводим задачу к меньшей, переходя к нахождению пути из $s$ в $p[t]$.

Реализация BFS с восстановлением пути

// теперь 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;
}

Проверка принадлежности вершины кратчайшему пути

Дан ориентированный граф $G$, найти все вершины, которые принадлежат хотя бы одному кратчайшему пути из $s$ в $t$.

Запустим из вершины $s$ в графе $G$ BFS — найдём расстояния $d_1$. Построим транспонированный граф $G^T$ — граф, в котором каждое ребро заменено на противоположное. Запустим из вершины $t$ в графе $G^T$ BFS — найдём расстояния $d_2$.

Теперь очевидно, что $v$ принадлежит хотя бы одному кратчайшему пути из $s$ в $t$ тогда и только тогда, когда $d_1(v) + d_2(v) = d_1(t)$ — это значит, что есть путь из $s$ в $v$ длины $d_1(v)$, а затем есть путь из $v$ в $t$ длины $d_2(v)$, и их суммарная длина совпадает с длиной кратчайшего пути из $s$ в $t$.

Кратчайший цикл в ориентированном графе

Найти цикл минимальной длины в ориентированном графе.

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

Итого, у нас $|V|$ запусков BFS, и каждый запуск работает за $O(|V| + |E|)$. Тогда общее время работы составляет $O(|V|^2 + |V| |E|)$. Если инициализировать массив $dist$ единожды, а после каждого запуска BFS возвращать исходные значения только для достижимых вершин, решение будет работать за $O(|V||E|)$.

Задача

Дан взвешенный ориентированный граф $G = (V, E)$, а также вершина $s$. Длина ребра $(u, v)$ равна $w(u, v)$. Длины всех рёбер неотрицательные.
Найти длину кратчайшего пути от $s$ до каждой из вершин графа. Длина пути — сумма длин рёбер в нём.

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

Алгоритм Дейкстры решает приведённую выше задачу. Он работает следующим образом.

1. Создать массив $dist$ расстояний. Изначально $dist[s] = 0$ и $dist[v] = infty$ для $v neq s$.
2. Создать булёв массив $used$, $used[v] = 0$ для всех вершин $v$ — в нём мы будем отмечать, совершалась ли релаксация из вершины.
3. Пока существует вершина $v$ такая, что $used[v] = 0$ и $dist[v] neq infty$, притом, если таких вершин несколько, то $v$ — вершина с минимальным $dist[v]$, делать следующее:
   1. Пометить, что мы совершали релаксацию из вершины $v$, то есть присвоить $used[v] = 1$.
   2. Рассматриваем все рёбра $(v, u) in E$. Для каждого ребра пытаемся сделать релаксацию: если $dist[v] + w(v, u) < dist[u]$, присвоить $dist[u] = dist[v] + w(v, u)$.

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

Посчитаем, за сколько работает алгоритм. Мы $V$ раз ищем вершину минимальным $dist$, поиск минимума у нас линейный за $O(V)$, отсюда $O(V^2)$. Обработка ребер у нас происходит суммарно за $O(E)$, потому что на каждое ребро мы тратим $O(1)$ действий. Так мы находим финальную асимптотику: $O(V^2 + E)$.

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

Рёбра будем хранить как pair<int, int>, где первое число пары — куда оно ведёт; а второе — длина ребра.

// 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 (и любой динамике).

Дейкстра на сете

Искать вершину с минимальным $dist$ можно гораздо быстрее, используя такую структуру данных как очередь с приоритетом. Нам нужно хранить пары $(dist, index)$ и уметь делать такие операции:

• Извлечь минимум (чтобы обработать новую вершину)
• Удалить вершину по индексу (чтобы уменьшить $dist$ до какого-то соседа)
• Добавить новую вершину (чтобы уменьшить $dist$ до какого-то соседа)

Для этого используют, например, кучу или сет. Удобно помимо сета хранить сам массив dist, который его дублирует, но хранит элементы по порядку. Тогда, чтобы заменить значение $(dist_1, u)$ на $(dist_2, u)$, нужно удалить из сета значение $(dist[u], u)$, сделать $dist[u] = dist_2;$ и добавить в сет $(dist[u], u)$.

Данный алгоритм будет работать за $V O(log V)$ извлечений минимума и $O(E log V)$ операций уменьшения расстояния до вершины (может быть сделано после каждого ребра). Поэтому алгоритм работает за $O(E log V)$.

Заметьте, что этот алгоритм не лучше и не хуже, чем без сета, который работает за $O(V^2 + E)$. Ведь если $E = O(V^2)$ (граф почти полный), то Дейкстра без сета работает быстрее, а если, наример, $E = O(V)$, то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.

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

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

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

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph.
Note: Length of a directed path is the number of edges in it. 
Examples: 
 

Input: N = 4, M = 5 
 

Output: 3 
The directed path 1->3->2->4 
Input: N = 5, M = 8 
 

Output: 3 

Simple Approach: A naive approach is to calculate the length of the longest path from every node using DFS. 
The time complexity of this approach is O(N²). 
Efficient Approach: An efficient approach is to use Dynamic Programming and DFS together to find the longest path in the Graph. 
Let dp[i] be the length of the longest path starting from the node i. Initially all positions of dp will be 0. We can call the DFS function from every node and traverse for all its children. The recursive formula will be: 
 

dp[node] = max(dp[node], 1 + max(dp[child1], dp[child2], dp[child3]..)) 
 

At the end check for the maximum value in dp[] array, which will be the longest path in the DAG.
Below is the implementation of the above approach:
 

C++

#include <bits/stdc++.h>

using namespace std;

void dfs(int node, vector<int> adj[], int dp[], bool vis[])

{

    vis[node] = true;

    for (int i = 0; i < adj[node].size(); i++) {

        if (!vis[adj[node][i]])

            dfs(adj[node][i], adj, dp, vis);

        dp[node] = max(dp[node], 1 + dp[adj[node][i]]);

    }

}

void addEdge(vector<int> adj[], int u, int v)

{

    adj[u].push_back(v);

}

int findLongestPath(vector<int> adj[], int n)

{

    int dp[n + 1];

    memset(dp, 0, sizeof dp);

    bool vis[n + 1];

    memset(vis, false, sizeof vis);

    for (int i = 1; i <= n; i++) {

        if (!vis[i])

            dfs(i, adj, dp, vis);

    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {

        ans = max(ans, dp[i]);

    }

    return ans;

}

int main()

{

    int n = 5;

    vector<int> adj[n + 1];

    addEdge(adj, 1, 2);

    addEdge(adj, 1, 3);

    addEdge(adj, 3, 2);

    addEdge(adj, 2, 4);

    addEdge(adj, 3, 4);

    cout << findLongestPath(adj, n);

    return 0;

}

Java

import java.util.ArrayList;

class Graph

{

    int vertices;

    ArrayList<Integer> edge[];

    Graph(int vertices)

    {

        this.vertices = vertices;

        edge = new ArrayList[vertices+1];

        for (int i = 0; i <= vertices; i++)

        {

            edge[i] = new ArrayList<>();

        }

    }

    void addEdge(int a,int b)

    {

        edge[a].add(b);

    }

    void dfs(int node, ArrayList<Integer> adj[], int dp[],

                                    boolean visited[])

    {

        visited[node] = true;

        for (int i = 0; i < adj[node].size(); i++)

        {

            if (!visited[adj[node].get(i)])

                dfs(adj[node].get(i), adj, dp, visited);

            dp[node] = Math.max(dp[node], 1 + dp[adj[node].get(i)]);

        }

    }

    int findLongestPath( int n)

    {

        ArrayList<Integer> adj[] = edge;

        int[] dp = new int[n+1];

        boolean[] visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++)

        {

            if (!visited[i])

                dfs(i, adj, dp, visited);

        }

        int ans = 0;

        for (int i = 1; i <= n; i++)

        {

            ans = Math.max(ans, dp[i]);

        }

        return ans;

    }

}

public class Main

{

    public static void main(String[] args)

    {

        int n = 5;

        Graph graph = new Graph(n);

        graph.addEdge( 1, 2);

        graph.addEdge( 1, 3);

        graph.addEdge( 3, 2);

        graph.addEdge( 2, 4);

        graph.addEdge( 3, 4);

        graph.findLongestPath(n);

        System.out.println( graph.findLongestPath( n));

    }

}

Python3

def dfs(node, adj, dp, vis):

    vis[node] = True

    for i in range(0, len(adj[node])): 

        if not vis[adj[node][i]]:

            dfs(adj[node][i], adj, dp, vis)

        dp[node] = max(dp[node], 1 + dp[adj[node][i]])

def addEdge(adj, u, v):

    adj[u].append(v)

def findLongestPath(adj, n):

    dp = [0] * (n + 1)

    vis = [False] * (n + 1)

    for i in range(1, n + 1): 

        if not vis[i]:

            dfs(i, adj, dp, vis)

    ans = 0

    for i in range(1, n + 1): 

        ans = max(ans, dp[i])

    return ans

if __name__ == "__main__":

    n = 5

    adj = [[] for i in range(n + 1)]

    addEdge(adj, 1, 2)

    addEdge(adj, 1, 3)

    addEdge(adj, 3, 2)

    addEdge(adj, 2, 4)

    addEdge(adj, 3, 4)

    print(findLongestPath(adj, n))

C#

using System;

using System.Collections.Generic;

class Graph

{

    public int vertices;

    public List<int> []edge;

    public Graph(int vertices)

    {

        this.vertices = vertices;

        edge = new List<int>[vertices + 1];

        for (int i = 0; i <= vertices; i++)

        {

            edge[i] = new List<int>();

        }

    }

    public void addEdge(int a, int b)

    {

        edge[a].Add(b);

    }

    public void dfs(int node, List<int> []adj,

                    int []dp, Boolean []visited)

    {

        visited[node] = true;

        for (int i = 0; i < adj[node].Count; i++)

        {

            if (!visited[adj[node][i]])

                dfs(adj[node][i], adj, dp, visited);

            dp[node] = Math.Max(dp[node], 1 +

                                dp[adj[node][i]]);

        }

    }

    public int findLongestPath( int n)

    {

        List<int> []adj = edge;

        int[] dp = new int[n + 1];

        Boolean[] visited = new Boolean[n + 1];

        for (int i = 1; i <= n; i++)

        {

            if (!visited[i])

                dfs(i, adj, dp, visited);

        }

        int ans = 0;

        for (int i = 1; i <= n; i++)

        {

            ans = Math.Max(ans, dp[i]);

        }

        return ans;

    }

}

class GFG

{

    public static void Main(String[] args)

    {

        int n = 5;

        Graph graph = new Graph(n);

        graph.addEdge( 1, 2);

        graph.addEdge( 1, 3);

        graph.addEdge( 3, 2);

        graph.addEdge( 2, 4);

        graph.addEdge( 3, 4);

        graph.findLongestPath(n);

        Console.WriteLine(graph.findLongestPath(n));

    }

}

Javascript

<script>

function dfs(node, adj, dp, vis)

{

    vis[node] = true;

    for (var i = 0; i < adj[node].length; i++) {

        if (!vis[adj[node][i]])

            dfs(adj[node][i], adj, dp, vis);

        dp[node] = Math.max(dp[node], 1 + dp[adj[node][i]]);

    }

}

function addEdge(adj, u, v)

{

    adj[u].push(v);

}

function findLongestPath(adj, n)

{

    var dp = Array(n+1).fill(0);

    var vis = Array(n+1).fill(false);

    for (var i = 1; i <= n; i++) {

        if (!vis[i])

            dfs(i, adj, dp, vis);

    }

    var ans = 0;

    for (var i = 1; i <= n; i++) {

        ans = Math.max(ans, dp[i]);

    }

    return ans;

}

var n = 5;

var adj = Array.from(Array(n+1), ()=>Array());

addEdge(adj, 1, 2);

addEdge(adj, 1, 3);

addEdge(adj, 3, 2);

addEdge(adj, 2, 4);

addEdge(adj, 3, 4);

document.write( findLongestPath(adj, n));

</script>

Time Complexity: O(N+M) 
Auxiliary Space: O(N) 
 

?list=PLqM7alHXFySEaZgcg7uRYJFBnYMLti-nh
 

Last Updated :
30 Dec, 2021

Like Article

Save Article

Пусть
–
граф (или псевдограф).

Расстояние в графе удовлетворяют
аксиомам метрики

1) 
,

2) 
 (не
в ориентированном графе)

3) 

4) 
 в
связном графе (не в ориентированном
графе).

Пусть
 связный
граф (или псевдограф).

• Определение
  Диаметром графа G
  называется величина
  .

Пусть
.

• Определение
  Максимальным удалением (эксцентриситетом)
  в графе G
  от вершины
   называется
  величина
  .

• Определение
  Радиусом графа G
  называется величина
  

• Определение
  Центром графа Gназывается
  любая вершина
   такая,
  что
  .

Алгоритм фронта волны

Пусть
 ориентированный
граф с n³2 вершинами и v,w
(v¹w)
– заданные вершины из V.

Алгоритм поиска
минимального пути из
 в

 в
ориентированном графе

(алгоритм
фронта волны).

1)     Помечаем
вершину
 индексом
0, затем помечаем вершины Î образу вершины

 индексом
1. Обозначаем их FW₁
(v).
Полагаем k=1.

2)       
Если
 или
k=n-1,
и одновременно
то вершина
 не
достижима из
.
Работа алгоритма заканчивается.

В противном случае продолжаем:

3)       
Если
,
то переходим к шагу 4.

В противном случае мы нашли
минимальный путь из
 в

 и
его длина равна k.
Последовательность вершин

                   

есть этот минимальный путь. Работа
завершается.

4)       
Помечаем индексом k+1
все непомеченные вершины, которые
принадлежат образу множества вершин c
индексом k.
Множество вершин с индексом k+1
обозначаем
.
Присваиваем k:=k+1
и переходим к 2).

• Замечания
  Множество
   называется
  фронтом волны k^го
  уровня.

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

.

Чтобы найти расстояния в
ориентированном графе, необходимо
составить матрицу минимальных расстояний
R(D)между
его вершинами. Это квадратная матрица
размерности
,
элементы главной диагонали которой
равны нулю (,
i=1,..,n).

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

Рассматриваем первую строку,
в которой есть единицы. Пусть это строка
− i-тая
и на пересечении с j-тым
столбцом стоит единица (то есть
).
Это значит, что из вершины
 можно
попасть в вершину
 за
один шаг. Рассматриваем j-тую
сроку (строку стоит вводить в рассмотрение,
если она содержит хотя бы одну единицу).
Пусть элемент
.
Тогда из вершины
 в
вершину
 можно
попасть за два шага.

Таким образом, можно записать

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

• Пример Найдем
  расстояния в ориентированном графе D,
  изображенном на рис. 7. В данной задаче
  количество вершин n=7,
  следовательно, матрицы смежности 
  и минимальных расстояний между вершинами
  ориентированного графа Dбудут
  иметь размерность 7×7.

Рис.7.

Матрица смежности:

                  

.

Начинаем заполнять матрицу
R(D)
минимальных расстояний: сначала ставим
нули по главной диагоналии r_ij=a_ij,
если a_ij=1,
(т.е. переносим единицы из матрицы
смежности). Рассматриваем первую строку.
Здесь есть две единицы, то есть из первой
вершины за один шаг можно попасть во
вторую и шестую. Из второй вершины можно
попасть за один шаг в третью (путь в
первую вершину нас не интересует),
следовательно, можно записать
.
Из шестой вершины можем добраться за
один шаг в пятую и седьмую, а значит,
,

.
Теперь ищем маршруты, исходящие из
первой вершины, состоящие из 3 шагов: за
2 шага идем в третью вершину, оттуда за
один шаг попадаем в четвертую, поэтому

.
В итоге получаем следующую матрицу:

                  

Таким образом, диаметром
исследуемого ориентированного графа
будет
.

Для каждой вершины заданного
ориентированного графа найдем максимальное
удаление (эксцентриситет) в графе G от
вершины нее по формуле, которая была
приведена выше
:
r(v_i)
− максимальное из расстояний, стоящих
в i-той
строке. Таким образом,

r(v₁)=3,
r(v₂)=3,
r(v₃)=5,
r(v₄)=4,
r(v₅)=2,
r(v₆)=2,
r(v₇)=3.

Значит, радиусом графа G
будет

Соответственно, центрами
графа G будут
вершины v₅
иv₆
, так как величины их эксцентриситетов
совпадают с величиной радиуса.

Опишем теперь нахождение
минимального пути из вершины v₃
в вершинуv₆
по алгоритму фронта волны. Обозначим
вершину v₃
как V₀,
а вершину v₆–
как W
(см. рис. 8). Множество вершин, принадлежащих
образу V₀,
состоит из одного элемента – это вершина
v₄,
которую, согласно алгоритму, обозначаем
как V₁:
FW₁(v₃)={v₄}.

Поскольку искомая вершина
не принадлежит фронту волны первого
уровня
,
продолжаем работу алгоритма. Строим
фронт волны второго уровня – это множество
вершин, принадлежащих образу вершиныV₁:
FW₂(v₃)={v₇},
обозначаем v₇≡V₂.
В образ вершины V₂
входят две вершины –v₅
и v₄,
но, так как v₄
уже была помечена как V₀,
то фронт волны третьего уровня состоит
из одного элемента: FW₃(v₃)={v₅},
v₅≡V₃.
Из непомеченных вершин в образ вершины
V₃
входят v₁
и v₂,
соответственно, FW₄(v₃)={v₁,
v₂},
v₁≡V₄,
v₂≡V₄.
Теперь помечены все вершины, кроме v₆,
которая входит в образ вершины
,
то есть FW₅(v₃)={v₆≡W},
работа алгоритма закончена. Минимальный
путь (5 шагов) из вершины v₃
в вершинуv₆
выглядит так: v₃v₄v₇v₅v₁v₆.

Рис.8.

Минимальный путь в
нагруженном ориентированном графе по
методу Форда-Беллмана

Найти минимальный путь в
нагруженном ориентированном графе из
вершины
 в
вершину
 по
методу Форда-Беллмана.

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

Пусть D=(V,X)
– нагруженный ориентированный граф,
V={v₁,…,v_n},
n>1.
Введем величины
,
где i=1,…,n,
k=0,1,2,…,n–1.

Для каждого фиксированного
i и
k
величина
 равна
длине минимального пути среди путей из
v_нач
в v_i
содержащих не более k
дуг. Если путей нет, то
.

Положим также
.

Составляем матрицу длин
дуг C(D)=[c_ij]
порядка n:

                    

Утверждение.
При i=2,…,n,
k³0
выполняется равенство

                     

.                 
(3.1)

Алгоритм Форда-Беллмана
нахождения минимального пути в нагруженном
ориентированном графе D из v_нач
в v_кон.(
v_нач
≠ v_кон).

(
записываем в виде матрицы, i–
строка, k-столбец).

1)     Составляем
таблицу
,
i=1,…,n,
k=0,…,n-1.
Если
,
то пути из v_нач
в v_кон
нет. Конец алгоритма.

2)     Если
 то
это число выражает длину любого
минимального пути из v_нач
в v_кон.
Найдем минимальное k₁³1,
при котором
.
По определению
 получим,
что k₁–
минимальное число дуг в пути среди всех
минимальных путей из v_начв
v_кон.

3)     Затем
определяем номера i₂,…,

 такие,
что

,

,

,

то есть восстанавливаем по
составленной таблице и матрице стоимости
искомый минимальный путь из v_нач
в v_кон.

• Пример

Найдем минимальный путь из
вершины v₂
в v₆
в ориентированном нагруженном графе
D,
изображенном на рис. 9. В рассматриваемом
графе количество вершин n=7,
следовательно, матрица длин дуг
ориентированного графа Dбудет
иметь размерность 7×7.

Рис.
9.

Матрица длин дуг для рассматриваемого
графа будет выглядеть следующим образом:

                

.

Согласно алгоритму, составляем
таблицу стоимости минимальных путей
из вершины v₂
в вершину v_i
не более, чем за k
шагов, k=0,…n-1
(n=7,
следовательно, k=0,…6).
Как было определено выше,
,
и
 для
всех остальных вершин v_i≠
v₂,
то есть первый столбец таблицы состоит
из элементов, равных
,
кроме элемента
.
Второй столбец таблицы повторяет вторую
строку матрицы стоимости, поскольку
представляет собой стоимость возможных
путей из вершины v₂
за один шаг. Далее по формуле (3.1) находим
по столбцам все оставшиеся элементы
таблицы. Например, чтобы найти элемент

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

В конечном итоге получаем следующую
таблицу:

             

Теперь необходимо по
построенной таблице и по матрице C(D)
восстановить минимальный путь из вершины
v₂
в v₆,
который будет строиться с конца, то
есть, начиная с вершины v6.
Для этого выбираем минимальное из чисел,
стоящих в строке, соответствующей v₆
в таблице. Это число – 21 – длина
минимального искомого пути. В первый
раз такая длина была получена при
количестве шагов, равном 4. В вершину v₆
мы можем попасть за один шаг из вершин
v₁
и v₇
(длина соответствующих дуг 8 и 5
соответственно – данные из матрицы
C(D)).
Выбираем минимальную по длине из этих
дуг. Далее, в вершину v₇
можно попасть из v₄
и v₅(длина
соответствующих дуг 7 и 3 соответственно).
Продолжая аналогичным образом, найдем
искомый путь за 4 шага минимальной длины
из вершины v₂
в v₆:
v₂v₃v₅v₇v₆.

78