Разбор задачи «Расстояния от штаба»

1. Идея

Нужно найти минимальное время пути из вершины 1 во все остальные вершины ориентированного графа с неотрицательными весами рёбер.

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

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

2. Наблюдения

1. Граф направленный, поэтому дорога u -> v не означает, что можно ехать обратно.

2. Нужно найти расстояния именно из вершины 1, а не между всеми парами вершин.

3. Веса рёбер неотрицательны: w >= 0. Это главное условие корректности алгоритма Дейкстры.

4. Ограничения большие:

   • n до 100000
   • m до 300000

   Значит, решение на матрице смежности или алгоритм Флойда не подходит. Нужен алгоритм примерно O((n + m) log n).

5. Если вершина недостижима из 1, её расстояние так и останется бесконечным, и для неё нужно вывести -1.

3. Алгоритм

Используем список смежности и очередь с приоритетом.

Шаги

1. Считываем n и m.
2. Строим список смежности: для каждой вершины храним список пар (to, w).
3. Создаём массив dist, где dist[v] — лучшее известное расстояние от 1 до v.
   • Изначально все значения бесконечны.
   • dist[1] = 0.
4. Помещаем в приоритетную очередь пару (0, 1).
5. Пока очередь не пуста:
   • Извлекаем вершину с минимальным текущим расстоянием.
   • Если это значение уже устарело и не равно dist[v], пропускаем.
   • Иначе пробуем расслабить все исходящие рёбра:
     • для ребра v -> to веса w
     • если dist[to] > dist[v] + w, то обновляем dist[to] и кладём новую пару в очередь.
6. После завершения:
   • если dist[i] осталось бесконечным, выводим -1;
   • иначе выводим dist[i].

4. Почему это работает

Алгоритм Дейкстры работает для графов с неотрицательными весами.

Основная идея корректности

Когда из очереди извлекается вершина v с расстоянием cur_dist, и это значение совпадает с dist[v], то это уже действительно кратчайшее расстояние до v.

Почему так?

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

После этого мы пытаемся улучшить расстояния до соседей вершины v. Это называется расслаблением рёбер.

Зачем нужна проверка if cur_dist != dist[v]

Одна и та же вершина может попасть в очередь несколько раз:

• сначала с более длинным расстоянием,
• потом с более коротким.

Когда мы достаём старую запись, она уже неактуальна. Проверка позволяет просто пропустить её.

Это не влияет на правильность, но делает алгоритм эффективным.

Что получится в итоге

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

• если существует путь из 1, в dist окажется длина кратчайшего пути;
• если пути нет, значение останется бесконечным, и мы выведем -1.

5. Сложность

Пусть:

• n — число вершин,
• m — число рёбер.

По времени

Алгоритм Дейкстры со списком смежности и кучей работает за `O((n + m) log n)``.

На практике часто пишут O(m log n), так как обычно m >= n.

По памяти

• список смежности: O(n + m)
• массив расстояний: O(n)
• очередь с приоритетом: O(m) в худшем случае

Итого: O(n + m) памяти.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    const long long INF = (long long)4e18;
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        long long cur_dist = pq.top().first;
        int v = pq.top().second;
        pq.pop();

        if (cur_dist != dist[v]) {
            continue;
        }

        for (auto edge : graph[v]) {
            int to = edge.first;
            int w = edge.second;
            if (dist[to] > dist[v] + w) {
                dist[to] = dist[v] + w;
                pq.push({dist[to], to});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << -1;
        } else {
            cout << dist[i];
        }
        if (i < n) {
            cout << ' ';
        }
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

import heapq

n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

INF = 10**30
dist = [INF] * (n + 1)
dist[1] = 0

pq = [(0, 1)]

while pq:
    cur_dist, v = heapq.heappop(pq)
    if cur_dist != dist[v]:
        continue

    for to, w in graph[v]:
        nd = cur_dist + w
        if nd < dist[to]:
            dist[to] = nd
            heapq.heappush(pq, (nd, to))

answer = []
for i in range(1, n + 1):
    if dist[i] == INF:
        answer.append("-1")
    else:
        answer.append(str(dist[i]))

print(" ".join(answer))