13.4 Поиск кратчайших путей в DAG¶

Введение¶

Ранее мы рассмотрели алгоритмы поиска кратчайших путей в общем графе: алгоритм Дейкстры и алгоритм Беллмана–Форда. Однако существует важный частный случай графов, где задачу можно решить значительно быстрее — ориентированные ациклические графы (DAG).

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

Идея алгоритма¶

Главная идея:

1. Выполнить топологическую сортировку графа.
2. Обрабатывать вершины в этом порядке.
3. Для каждой вершины "расслаблять" (relax) её исходящие рёбра.

Почему это работает?

Потому что:

• в DAG нет циклов,
• значит, все пути идут строго в одном направлении,
• и когда мы обрабатываем вершину, все кратчайшие пути до неё уже найдены.

Связь с алгоритмом Дейкстры¶

Перед тем как идти дальше, важно вспомнить идею алгоритма Дейкстры.

Идея Дейкстры¶

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

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

Интуитивно: мы как будто “расширяем волну” от стартовой вершины.

Почему это работает¶

Если веса неотрицательные:

• более короткий путь не может появиться позже,
• значит, как только мы выбрали вершину — её расстояние окончательно.

Ограничение¶

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

• не работает с отрицательными весами.

Почему в DAG проще¶

В DAG нам не нужно выбирать минимальную вершину.

Почему?

Потому что:

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

Это делает алгоритм:

• проще,
• быстрее,
• универсальнее (работает даже с отрицательными весами!).

Алгоритм¶

1. Найти топологический порядок вершин.

2. Инициализировать расстояния:

3. dist[s] = 0

4. остальные = бесконечность

5. Пройти вершины в топологическом порядке:

6. для каждой вершины v:

   • для каждого ребра v → u:

   • dist[u] = min(dist[u], dist[v] + w)

Пример¶

Рассмотрим граф:

mermaid graph LR A -->|2| B A -->|5| C B -->|1| C B -->|3| D C -->|2| D

Стартовая вершина: A

Шаг 1: топологический порядок¶

Один из вариантов: A → B → C → D

Шаг 2: расчёт¶

Изначально:

• dist[A] = 0
• остальные = ∞

Обрабатываем:

A:

• B = 2
• C = 5

B:

• C = min(5, 2+1=3) → 3
• D = 2+3=5

C:

• D = min(5, 3+2=5) → 5

D:

• нет изменений

Ответ:¶

• A = 0
• B = 2
• C = 3
• D = 5

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

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<vector<pair<int,int>>> g;
vector<int> used, order;

void dfs(int v) {
used[v] = 1;
for (auto to : g[v]) {
if (!used[to.first]) dfs(to.first);
}
order.push_back(v);
}

int main() {
cin >> n >> m;
g.resize(n);

for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    g[a].push_back({b, w});
}

used.assign(n, 0);

for (int i = 0; i < n; i++) {
    if (!used[i]) dfs(i);
}

reverse(order.begin(), order.end());

const int INF = 1e9;
vector<int> dist(n, INF);

int s;
cin >> s;
dist[s] = 0;

for (int v : order) {
    if (dist[v] == INF) continue;
    for (auto to : g[v]) {
        int u = to.first;
        int w = to.second;
        if (dist[u] > dist[v] + w) {
            dist[u] = dist[v] + w;
        }
    }
}

for (int i = 0; i < n; i++) {
    if (dist[i] == INF) cout << "INF ";
    else cout << dist[i] << " ";
}

}

Сложность¶

• Топологическая сортировка: O(n + m)
• Основной проход: O(m)

Итого: O(n + m)

Это быстрее, чем:

• Дейкстра: O((n + m) log n)
• Беллман–Форд: O(n · m)

Когда использовать¶

Используйте этот алгоритм, если:

• граф ориентированный,
• нет циклов (DAG),
• нужно найти кратчайшие пути,
• веса могут быть даже отрицательными.

Типичные ошибки¶

1. Граф не является DAG¶

Если есть цикл:

• топологическая сортировка невозможна,
• алгоритм работает некорректно.

2. Неправильный порядок¶

Если вершины обрабатываются не в топологическом порядке:

• можно получить неверные расстояния.

3. Забыли проверку INF¶

Если не проверить: dist[v] == INF

то можно: распространить мусорные значения.

4. Перепутаны направления рёбер¶

В DAG важно:

• правильно задать направление,
• иначе порядок нарушится.

Итог¶

Алгоритм для DAG — это:

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

Интуитивно: мы просто “проходим граф слева направо” и постепенно улучшаем ответы.