Single-Source Shortest Path

Идея — жадная: поддерживать множество вершин с уже точно известным кратчайшим расстоянием от старта, и на каждом шаге добавлять в это множество вершину с минимальной оценкой расстояния среди ещё не добавленных (используя приоритетную очередь / min-heap). Корректность держится на том, что при неотрицательных весах расстояние до самой близкой ещё не обработанной вершины уже не может уменьшиться позже — если бы существовал более короткий путь к ней через ещё не обработанную вершину, эта вершина была бы ближе, что противоречит выбору минимума.The idea is greedy: maintain a set of vertices whose shortest distance from the source is already known for certain, and at each step add the vertex with the minimum distance estimate among those not yet added (using a priority queue / min-heap). Correctness rests on the fact that with non-negative weights, the distance to the closest not-yet-processed vertex can never decrease later — if a shorter path to it existed through another not-yet-processed vertex, that vertex would have to be closer, contradicting the choice of the minimum.

std::vector<long long> dijkstra(int n, int src,
    const std::vector<std::vector<std::pair<int,int>>>& adj) { // (сосед, вес)// (neighbor, weight)
    std::vector<long long> dist(n, LLONG_MAX);
    std::priority_queue<std::pair<long long,int>,
        std::vector<std::pair<long long,int>>, std::greater<>> pq;
    dist[src] = 0; pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;              // устаревшая запись в куче// a stale heap entry
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Сложность с бинарной кучей — O((V+E) log V); с Fibonacci heap теоретически лучше — O(E + V log V), так как decrease-key там амортизированно O(1) вместо O(log V) — на практике константы Fibonacci heap делают её выигрышной только на очень больших разреженных графах, и большинство реальных реализаций (включая стандартные библиотеки) используют обычную бинарную кучу.Complexity with a binary heap is O((V+E) log V); with a Fibonacci heap it's theoretically better — O(E + V log V), since decrease-key there is amortized O(1) instead of O(log V) — in practice, a Fibonacci heap's constants only pay off on very large sparse graphs, and most real implementations (including standard libraries) use a plain binary heap.

Дейкстра ломается на отрицательных весах, потому что жадное предположение "обработанная вершина больше не изменится" перестаёт быть верным — более длинный по числу рёбер, но более "дешёвый" из-за отрицательного веса путь может появиться позже. Беллман-Форд решает это без жадности: V-1 раз проходит по всем рёбрам графа, пытаясь "расслабить" (relax) каждое — уменьшить dist[v], если dist[u] + вес(u,v) < dist[v]. V-1 итераций достаточно, потому что кратчайший путь в графе без отрицательных циклов не может содержать больше V-1 рёбер.Dijkstra breaks on negative weights because the greedy assumption "a settled vertex will never change" stops holding — a path with more edges but a cheaper total due to a negative weight can appear later. Bellman-Ford solves this without greediness: it passes over all of the graph's edges V-1 times, trying to "relax" each one — decreasing dist[v] if dist[u] + weight(u,v) < dist[v]. V-1 iterations suffice because a shortest path in a graph with no negative cycles can't contain more than V-1 edges.

Побочный эффект, который часто и есть настоящая причина использовать этот алгоритм: детекция отрицательных циклов. Если после V-1 итераций хотя бы одно ребро всё ещё можно расслабить, значит в графе есть цикл с отрицательной суммой весов, и понятие "кратчайший путь" для него не определено (можно бесконечно уменьшать стоимость, проходя цикл снова и снова).A side effect that's often the actual reason to use this algorithm: negative-cycle detection. If after V-1 iterations at least one edge can still be relaxed, the graph contains a cycle with a negative total weight, and "shortest path" is undefined for it (cost can be decreased indefinitely by looping through the cycle again and again).

bool bellmanFord(int n, int src, std::vector<std::array<int,3>>& edges,
    std::vector<long long>& dist) {  // edges: {u, v, weight}// edges: {u, v, weight}
    dist.assign(n, LLONG_MAX); dist[src] = 0;
    for (int i = 0; i < n - 1; ++i)
        for (auto& [u, v, w] : edges)
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
    for (auto& [u, v, w] : edges)                // V-й проход — детект цикла// V-th pass — cycle check
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) return false;
    return true;
}

Наблюдение: Беллман-Форд честно проходит все E рёбер на каждой из V-1 итераций, даже когда абсолютное большинство рёбер давно не меняются. SPFA — оптимизация через очередь: вершина добавляется в очередь на обработку только если её dist только что уменьшился, и обрабатываются только вершины из очереди, а не все рёбра подряд. В среднем на практике это заметно быстрее O(VE), хотя в худшем случае (специально сконструированный граф) сложность остаётся O(VE) — по этой причине SPFA не имеет гарантий лучше Беллмана-Форда и на соревнованиях по алгоритмам считается риском, а не безопасной заменой.The observation: Bellman-Ford dutifully scans all E edges on each of its V-1 iterations, even when the vast majority of edges haven't changed in a while. SPFA optimizes via a queue: a vertex is enqueued for processing only when its dist has just decreased, and only queued vertices are processed, not every edge in sequence. On average, in practice, this is noticeably faster than O(VE), though in the worst case (a specially constructed graph) the complexity remains O(VE) — for this reason SPFA carries no better guarantee than Bellman-Ford, and in competitive programming it's treated as a risk, not a safe drop-in replacement.

• cp-algorithms — Dijkstra
• cp-algorithms — Bellman-Ford