Кратчайшие пути: Дейкстра и Флойд

Кратчайшие пути во взвешенном графе: Дейкстра с кучей за O(m log n) и Флойд за O(n³).

Когда у рёбер появляются веса (длины дорог, стоимости), BFS уже не работает. Два главных инструмента: • Дейкстра — кратчайшие пути от одной вершины до всех, O(m log n) с приоритетной очередью. Ограничение: веса неотрицательны. • Флойд — кратчайшие пути между ВСЕМИ парами, O(n³), пять строк кода. Годится при n до нескольких сотен. Идея Дейкстры: поддерживаем текущие лучшие расстояния и всегда «закрываем» ближайшую из открытых вершин — при неотрицательных весах её расстояние уже никогда не улучшится.

Попробуйте сами — код можно менять

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

const long long INF = 1e18;

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<std::pair<int, long long>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long w;
        std::cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

std::vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    std::priority_queue<std::pair<long long, int>,
                        std::vector<std::pair<long long, int>>,
                        std::greater<>> pq;
    pq.push({0, 1});

while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > dist[v]) continue; // устаревшая запись - пропускаем

for (auto [to, w] : g[v]) {
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                pq.push({dist[to], to});
            }
        }
    }

for (int v = 1; v <= n; v++) {
        std::cout << "до " << v << ": " << dist[v] << "\n";
    }
    return 0;
}

Входные данные (пример — можно менять)

Дейкстра. Введите: 5 6, затем рёбра «a b вес»: 1 2 2, 1 3 5, 2 3 1, 2 4 4, 3 5 1, 4 5 3

Ключевая строка — if (d > dist[v]) continue: в очереди могут лежать устаревшие записи (мы кладём вершину повторно при каждом улучшении), и их надо молча пропускать. Без этой строки алгоритм остаётся верным, но может сильно замедлиться. Флойд ещё проще: три вложенных цикла, внешний — по «промежуточной» вершине k. После итерации k массив d[i][j] хранит кратчайшие пути, использующие промежуточные вершины только из {1..k}.

Попробуйте сами — код можно менять

Входные данные (пример — можно менять)

Флойд: все пары. Введите: 4 4, затем: 1 2 5, 2 3 3, 3 4 1, 1 3 10

Для отрицательных рёбер (без отрицательных циклов) существует алгоритм Беллмана-Форда за O(n·m) — познакомьтесь с ним самостоятельно, когда встретите такую задачу. Задание: в примере Дейкстры проверьте руками, что расстояние до вершины 4 равно 6, а до 5 — 4, проследив пути. Отметьте урок пройденным и переходите к минимальному остову.