Shortest Paths: Dijkstra and Floyd

Shortest paths in a weighted graph: Dijkstra with a heap in O(m log n) and Floyd in O(n³).

Once edges get weights (road lengths, costs), BFS no longer works. The two main tools: • Dijkstra — shortest paths from one vertex to all others, O(m log n) with a priority queue. Restriction: weights must be non-negative. • Floyd — shortest paths between ALL pairs, O(n³), five lines of code. Fine for n up to a few hundred. Dijkstra's idea: maintain the current best distances and always "close" the nearest open vertex — with non-negative weights its distance can never improve again.

Try it yourself — the code is editable

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

Input (sample — feel free to edit)

Dijkstra. Enter: 5 6, then "a b weight" edges: 1 2 2, 1 3 5, 2 3 1, 2 4 4, 3 5 1, 4 5 3

The key line is if (d > dist[v]) continue: the queue may contain stale entries (we re-insert a vertex on every improvement), and they must be silently skipped. Without this line the algorithm stays correct but can slow down badly. Floyd is even simpler: three nested loops, the outer one over the "intermediate" vertex k. After iteration k, the array d[i][j] holds shortest paths using intermediate vertices only from {1..k}.

Try it yourself — the code is editable

Input (sample — feel free to edit)

Floyd: all pairs. Enter: 4 4, then: 1 2 5, 2 3 3, 3 4 1, 1 3 10

For negative edges (without negative cycles) there is the Bellman-Ford algorithm at O(n·m) — get to know it on your own when you meet such a problem. Task: in the Dijkstra example, verify by hand that the distance to vertex 4 is 6 and to vertex 5 is 4, tracing the paths. Mark the lesson as completed and move on to the minimum spanning tree.