Shortest Paths: Dijkstra, 0-1 BFS, Bellman-Ford and Floyd-Warshall

Four shortest-path algorithms, the constraints that pick one, and the bugs that make them slow or wrong without any visible error, each shown failing and then fixed.

Four problems that look the same

Here are four problems. Each asks for the cheapest way to get from one place to another, and each needs a different algorithm.

A delivery network has 2*10^5 junctions and 4*10^5 one-way roads, each with a travel time in minutes. Find the fastest time from the depot to every junction.
Between 10^5 servers some links are already licensed and free to use; every other link needs one license. Find the fewest licenses needed to reach each server from server 1.
A game map has 500 rooms and 5000 corridors. Some corridors are time portals that move you back in time, so their cost is negative. Find the earliest arrival in each room, and notice when a room can be reached arbitrarily early.
A transit planner has 300 stops and must answer 10^5 questions of the form "fastest route from stop a to stop b", with the route itself, not just its length.

The breadth-first search from Graphs: BFS, DFS, Connected Components and Topological Sort solves none of them, because BFS counts edges and these edges have different costs. The algorithms in this lesson are the four standard answers: Dijkstra for problem 1, 0-1 BFS for problem 2, Bellman-Ford for problem 3 and Floyd-Warshall for problem 4. The interesting part is less the algorithms themselves than the reasons each one fits its problem, and the bugs that make a correct-looking implementation slow or wrong.

Throughout, V is the number of vertices, E the number of edges, and a path's length is the sum of its edge weights. Programs read input through solve(std::istream&, std::ostream&) as described in Fast I/O, Contest Templates and Stress Testing: main feeds an embedded sample, and on a judge you call solve(std::cin, std::cout) and nothing else changes.

Choosing by weights and sizes

Two questions decide the algorithm: what the edge weights can be, and whether you need distances from one source or between all pairs.

Situation	Algorithm	Time
one source, weights `>= 0`	Dijkstra with a binary heap	`O((V + E) log V)`
one source, weights `0` or `1`	0-1 BFS	`O(V + E)`
one source, negative weights allowed	Bellman-Ford	`O(V * E)`
all pairs, `V` up to a few hundred	Floyd-Warshall	`O(V^3)`

Read problem 1 with the course's complexity table in mind: E = 4*10^5 and log V about 18 give a few million heap steps, which is comfortable. Bellman-Ford on the same graph would need up to V * E = 8*10^10 edge checks, far too many. Problem 3 has V * E = 2.5*10^6, so Bellman-Ford is fine there, and it is the only one of the three single-source methods that handles negative edges with a polynomial bound. Problem 4 has V^3 = 2.7*10^7: one Floyd-Warshall run answers every later question by table lookup.

The table is a starting point, not a law. Unit weights everywhere means plain BFS. Non-negative weights with all pairs and V = 2000 means running Dijkstra from every vertex, V times O(E log V), rather than V^3 = 8*10^9.

Dijkstra: settle the closest vertex first

Dijkstra's algorithm, published by Edsger W. Dijkstra in 1959, rests on one observation. Suppose all weights are non-negative and you already know the true distance of some set of vertices. Among the vertices you can reach by one more edge, take the one with the smallest tentative distance. No other route can beat it later, because every other route leaves the known set through a vertex that is already at least as far away, and the rest of that route adds a non-negative amount.

So the algorithm keeps a tentative distance dist[v] for every vertex, starting at 0 for the source and infinity elsewhere, and repeats: take the unsettled vertex with the smallest dist, settle it, and relax its outgoing edges. Relaxing the edge u -> v with weight w means: if dist[u] + w < dist[v], set dist[v] = dist[u] + w.

Trace it on the sample below, source 1. The edges from 1 give dist[2] = 7 and dist[3] = 2. Vertex 3 is closest, so it is settled, and its edges improve dist[2] to 5 and set dist[4] = 11. Now 2 is closest at 5; its edge to 4 improves dist[4] to 6. Then 4 is settled at 6 and sets dist[5] = 10. Vertex 6 has an edge to 1 but none into it, so it stays at infinity.

To find the closest vertex quickly, use a min-heap: std::priority_queue with std::greater<> and entries (distance, vertex). std::priority_queue has no "decrease key" operation, so when a distance improves we push a new entry and leave the old one in the heap. When an entry comes out whose distance no longer matches dist[v], it is stale and is skipped. This is called lazy deletion. Note the contrast with BFS in lesson 3, where a vertex is marked the moment it is pushed: in Dijkstra a pushed distance is only a candidate, and a vertex's distance is final when its non-stale entry is popped.

6 8 1        n m source; then m lines "u v w" for the edge u -> v
1 2 7
1 3 2
3 2 3
2 4 1
3 4 9
4 5 4
5 4 1
6 1 3

main.cppc++23

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <sstream>
#include <utility>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;

struct Edge { int to; ll w; };

std::vector<ll> dijkstra(const std::vector<std::vector<Edge>>& adj, int src) {
    std::vector<ll> dist(adj.size(), kInf);
    // (distance, vertex): pairs compare by .first first, so the closest pops first
    std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, 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;  // stale entry: u was improved after this push
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

void solve(std::istream& in, std::ostream& out) {
    int n, m, src;
    in >> n >> m >> src;
    std::vector<std::vector<Edge>> adj(n + 1);  // vertices are 1..n
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        in >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    auto dist = dijkstra(adj, src);
    for (int v = 1; v <= n; ++v) out << (dist[v] == kInf ? -1 : dist[v]) << '\n';
}

int main() {
    std::istringstream in(R"(6 8 1
1 2 7
1 3 2
3 2 3
2 4 1
3 4 9
4 5 4
5 4 1
6 1 3
)");
    solve(in, std::cout);  // on a judge: solve(std::cin, std::cout)
}

Output

Press Run to compile and run this example.

The cost: every successful relaxation pushes one entry, so the heap holds at most E + 1 entries and there are at most that many pops. Each push or pop costs O(log E), and log E <= 2 log V for a graph without parallel edges, so the total is O((V + E) log V). Each vertex's edges are scanned once, when its non-stale entry is popped.

Two details in the code carry the correctness. kInf is std::numeric_limits<ll>::max() / 4, the course's shared definition, so dist[u] + w never overflows for a finite dist[u]; more on that in the pitfalls. And the heap entries put the distance first, because std::pair compares its first member before its second.

Why a negative edge breaks Dijkstra

The argument above needed "the rest of that route adds a non-negative amount". With a negative edge, a vertex that is settled early can later be beaten by a route through a vertex that was farther away. Here is the smallest version: from 0, vertex 1 costs 2 directly, but 0 -> 2 -> 1 costs 5 - 4 = 1. This program uses the textbook form of Dijkstra, which marks a vertex final the moment it is popped, and compares it with Bellman-Ford (introduced below).

main.cppc++23

#include <functional>
#include <limits>
#include <print>
#include <queue>
#include <utility>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;
struct Edge { int to; ll w; };
using Graph = std::vector<std::vector<Edge>>;
using MinHeap = std::priority_queue<std::pair<ll, int>,
                                    std::vector<std::pair<ll, int>>, std::greater<>>;

// Textbook form: a vertex is final the moment it is popped.
std::vector<ll> dijkstraFinal(const Graph& g, int src) {
    std::vector<ll> dist(g.size(), kInf);
    std::vector<bool> done(g.size(), false);
    MinHeap pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (done[u]) continue;
        done[u] = true;
        for (auto [v, w] : g[u])
            if (!done[v] && dist[u] + w < dist[v]) pq.push({dist[v] = dist[u] + w, v});
    }
    return dist;
}

std::vector<ll> bellmanFord(const Graph& g, int src) {
    std::vector<ll> dist(g.size(), kInf);
    dist[src] = 0;
    for (std::size_t round = 1; round < g.size(); ++round)
        for (std::size_t u = 0; u < g.size(); ++u)
            if (dist[u] != kInf)
                for (auto [v, w] : g[u]) dist[v] = std::min(dist[v], dist[u] + w);
    return dist;
}

int main() {
    // 0 -> 1 costs 2; going through 2 costs 5 - 4 = 1, but 2 is popped last.
    Graph g(4);
    g[0] = {{1, 2}, {2, 5}};
    g[2] = {{1, -4}};
    g[1] = {{3, 1}};
    auto wrong = dijkstraFinal(g, 0), right = bellmanFord(g, 0);
    for (int v = 0; v < 4; ++v)
        std::println("vertex {}: dijkstra {:>2}   bellman-ford {:>2}", v, wrong[v],
                     right[v]);
}

Output

Press Run to compile and run this example.

vertex 0: dijkstra  0   bellman-ford  0
vertex 1: dijkstra  2   bellman-ford  1
vertex 2: dijkstra  5   bellman-ford  5
vertex 3: dijkstra  3   bellman-ford  2

Vertex 1 was popped and settled at 2 before vertex 2 was ever popped. When the cheaper route appeared, 1 was already final, so neither it nor vertex 3 behind it was corrected.

The lazy version from the previous section does not have a done array. It re-expands any vertex whose distance improves, so on graphs with negative edges but no negative cycle it still ends with the right distances. It just stops being Dijkstra in cost: a vertex can be expanded many times. This program builds a family of acyclic graphs with negative edges in which each level adds two vertices and forces the whole inner graph to be expanded twice, and counts expansions.

main.cppc++23

#include <functional>
#include <limits>
#include <print>
#include <queue>
#include <utility>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;
struct Edge { int to; ll w; };
using Graph = std::vector<std::vector<Edge>>;

// Lazy Dijkstra; returns how many times a vertex was expanded (popped and not stale).
long expansions(const Graph& g, int src) {
    std::vector<ll> dist(g.size(), kInf);
    std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>,
                        std::greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    long count = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        ++count;
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) pq.push({dist[v] = d + w, v});
    }
    return count;
}

// Level k: a new source s with s -> inner (0), s -> a (k), a -> inner (-k - 2^k).
// The detour through a is found late and is 2^k cheaper, so the whole inner
// graph is expanded a second time. No negative cycles: the graph is acyclic.
int build(Graph& g, int k) {
    int s = int(g.size());
    g.emplace_back();
    if (k == 0) return s;
    int a = s + 1;
    g.emplace_back();
    int inner = build(g, k - 1);
    g[s] = {{inner, 0}, {a, k}};
    g[a] = {{inner, -k - (ll{1} << k)}};
    return s;
}

int main() {
    for (int k = 4; k <= 20; k += 4) {
        Graph g;
        int src = build(g, k);
        std::println("vertices {:>2}: {:>8} expansions", g.size(), expansions(g, src));
    }
}

Output

Press Run to compile and run this example.

vertices  9:       46 expansions
vertices 17:      766 expansions
vertices 25:    12286 expansions
vertices 33:   196606 expansions
vertices 41:  3145726 expansions

Every 8 extra vertices multiply the work by about 16; the count is exactly 3 * 2^k - 2 for 2k + 1 vertices. So with negative edges, use Bellman-Ford and know its bound, rather than a heap algorithm whose worst case is exponential.

0-1 BFS: a deque instead of a heap

When every weight is 0 or 1, the heap is more machinery than needed. Dijkstra pops vertices in nondecreasing order of distance; with 0/1 weights, at any moment the vertices waiting to be expanded have only two distinct distances, some d and d + 1. A deque keeps them in order for free: a vertex reached by a 0-edge has the same distance as the current one, so it goes to the front; a vertex reached by a 1-edge goes to the back.

Problem 2 from the start of the lesson is exactly this shape. A licensed link costs 0, an unlicensed one costs 1, and the answer for a server is the fewest unlicensed links on any route to it.

7 7          n m; then m lines "u v needsLicense", links work both ways
1 2 1
1 3 0
3 4 0
4 2 0
2 5 1
4 5 1
6 7 0

main.cppc++23

#include <deque>
#include <iostream>
#include <limits>
#include <sstream>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;
struct Edge { int to; int w; };  // w is 0 or 1

std::vector<ll> zeroOneBfs(const std::vector<std::vector<Edge>>& adj, int src) {
    std::vector<ll> dist(adj.size(), kInf);
    std::deque<int> dq;
    dist[src] = 0;
    dq.push_back(src);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                // A 0-edge keeps v at u's distance: it goes first.
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    return dist;
}

void solve(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    std::vector<std::vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, needsLicense;
        in >> u >> v >> needsLicense;
        adj[u].push_back({v, needsLicense});  // links work both ways
        adj[v].push_back({u, needsLicense});
    }
    auto dist = zeroOneBfs(adj, 1);
    for (int v = 1; v <= n; ++v) out << (dist[v] == kInf ? -1 : dist[v]) << ' ';
    out << '\n';
}

int main() {
    std::istringstream in(R"(7 7
1 2 1
1 3 0
3 4 0
4 2 0
2 5 1
4 5 1
6 7 0
)");
    solve(in, std::cout);  // on a judge: solve(std::cin, std::cout)
}

Output

Press Run to compile and run this example.

0 0 0 0 1 -1 -1

Server 2 costs nothing even though the direct link 1 - 2 needs a license: the route 1 - 3 - 4 - 2 uses only licensed links. Servers 6 and 7 are linked to each other but not to 1, so both print -1.

Every push follows a successful relaxation and every edge is looked at when its tail is expanded, so 0-1 BFS runs in O(V + E). It also works when the weights are 0 and some fixed c > 0, since dividing by c gives 0/1. For small integer weights up to some k, the same bucket idea generalizes (Dial's algorithm), but for general weights, go back to the heap.

Bellman-Ford: relax everything, V - 1 times

Bellman-Ford needs no ordering at all. It relaxes every edge, then does it again, V - 1 times. The algorithm carries the names of Lester Ford, who described it in 1956, and Richard Bellman, who published it in 1958.

Why V - 1 rounds are enough: after round i, dist[v] is at most the length of the shortest path to v that uses at most i edges. Induct on i: the last edge of such a path is relaxed in round i, and its tail already had the right value after round i - 1. If there is no negative cycle, some shortest path is simple, and a simple path has at most V - 1 edges.

If there is a negative cycle reachable from the source, going around it makes paths ever cheaper, and "shortest" has no value for any vertex that the cycle can reach. Bellman-Ford detects this: after V - 1 rounds every distance is final unless a negative cycle exists, so any edge that still relaxes proves one. The program below handles problem 3. It marks vertices that can be reached arbitrarily cheaply as -inf by running more rounds in which any improvement, or any edge out of a -inf vertex, spreads -inf.

7 8          n m; then m lines "u v w" for the corridor u -> v (w may be negative)
1 2 4
1 3 6
2 3 -3
3 4 2
4 5 -1
5 6 3
6 5 -4
7 1 1

main.cppc++23

#include <iostream>
#include <limits>
#include <sstream>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;
struct Arc { int from, to; ll w; };

// dist[v] == kInf: unreachable; dist[v] == -kInf: arbitrarily small (a negative
// cycle lies on some path from src to v).
std::vector<ll> bellmanFord(int n, const std::vector<Arc>& arcs, int src) {
    std::vector<ll> dist(n + 1, kInf);
    dist[src] = 0;
    for (int round = 1; round <= n - 1; ++round) {
        bool changed = false;
        for (auto [u, v, w] : arcs) {
            if (dist[u] == kInf) continue;  // never relax out of an unreached vertex
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) break;  // nothing moved: every distance is final
    }
    // Anything that still improves is fed by a negative cycle; spread -inf.
    for (int round = 1; round <= n; ++round) {
        for (auto [u, v, w] : arcs) {
            if (dist[u] == kInf) continue;
            if (dist[u] == -kInf || dist[u] + w < dist[v]) dist[v] = -kInf;
        }
    }
    return dist;
}

void solve(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    std::vector<Arc> arcs(m);
    for (auto& [u, v, w] : arcs) in >> u >> v >> w;
    auto dist = bellmanFord(n, arcs, 1);
    for (int v = 1; v <= n; ++v) {
        out << "room " << v << ": ";
        if (dist[v] == kInf) out << "unreachable\n";
        else if (dist[v] == -kInf) out << "-inf\n";
        else out << dist[v] << '\n';
    }
}

int main() {
    std::istringstream in(R"(7 8
1 2 4
1 3 6
2 3 -3
3 4 2
4 5 -1
5 6 3
6 5 -4
7 1 1
)");
    solve(in, std::cout);  // on a judge: solve(std::cin, std::cout)
}

Output

Press Run to compile and run this example.

room 1: 0
room 2: 4
room 3: 1
room 4: 3
room 5: -inf
room 6: -inf
room 7: unreachable

Rooms 5 and 6 form a cycle of total cost 3 - 4 = -1, so each lap makes both cheaper and they print -inf. Room 7 has a corridor to 1 but none into it. The other rooms have ordinary distances; room 3 is cheapest through the portal from 2.

The cost is O(V * E) in the worst case. The changed flag lets the first phase stop early once a round changes nothing, which often helps on real inputs but does not change the worst case. The second phase runs V more rounds: enough for -inf to travel along any simple path.

Floyd-Warshall: all pairs in three loops

For all-pairs distances on a small graph, Floyd-Warshall is the shortest code in this lesson. Robert Floyd and Stephen Warshall published it in 1962; Bernard Roy had published essentially the same algorithm in 1959.

The idea is dynamic programming over which vertices a path may pass through. Number the vertices 0 to V - 1. After processing vertex k, d[i][j] is the shortest path from i to j whose intermediate vertices all come from 0..k. Allowing k as well either changes nothing or gives a path i -> ... -> k -> ... -> j whose two halves use only 0..k-1, so d[i][j] = min(d[i][j], d[i][k] + d[k][j]). That is why k must be the outermost loop: when k is processed, the two halves must already be complete for every pair.

To print the route, keep nxt[i][j], the first vertex after i on the best known path. It starts as j for a direct edge and is copied from nxt[i][k] whenever a path through k wins. This sample uses 0-indexed stops.

5 7          n m; then m lines "u v w"; then q and q queries "a b"
0 1 5
0 2 1
2 1 2
1 3 1
2 3 7
3 0 2
4 3 1
3
0 3
3 1
0 4

main.cppc++23

#include <format>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;

void solve(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    // d[i][j]: best known distance; nxt[i][j]: first step on that path (-1: none)
    std::vector d(n, std::vector<ll>(n, kInf));
    std::vector nxt(n, std::vector<int>(n, -1));
    for (int i = 0; i < n; ++i) d[i][i] = 0, nxt[i][i] = i;
    for (int e = 0; e < m; ++e) {
        int u, v;
        ll w;
        in >> u >> v >> w;
        if (w < d[u][v]) d[u][v] = w, nxt[u][v] = v;  // keep the cheaper parallel edge
    }
    for (int k = 0; k < n; ++k)          // k outermost: paths through 0..k only
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (d[i][k] < kInf && d[k][j] < kInf && d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    nxt[i][j] = nxt[i][k];
                }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            out << (d[i][j] == kInf ? std::string("  .") : std::format("{:>3}", d[i][j]));
        out << '\n';
    }
    int queries;
    in >> queries;
    while (queries--) {
        int a, b;
        in >> a >> b;
        if (nxt[a][b] == -1) { out << a << " -> " << b << ": no path\n"; continue; }
        out << a << " -> " << b << " (" << d[a][b] << "):";
        for (int v = a; v != b; v = nxt[v][b]) out << ' ' << v;
        out << ' ' << b << '\n';
    }
}

int main() {
    std::istringstream in(R"(5 7
0 1 5
0 2 1
2 1 2
1 3 1
2 3 7
3 0 2
4 3 1
3
0 3
3 1
0 4
)");
    solve(in, std::cout);  // on a judge: solve(std::cin, std::cout)
}

Output

Press Run to compile and run this example.

  0  3  1  4  .
  3  0  4  1  .
  5  2  0  3  .
  2  5  3  0  .
  3  6  4  1  0
0 -> 3 (4): 0 2 1 3
3 -> 1 (5): 3 0 2 1
0 -> 4: no path

The matrix row i lists distances from i; . means unreachable. The route 0 -> 3 has length 4 through 2 and 1, even though there are direct-looking alternatives (0 -> 1 -> 3 costs 6).

Floyd-Warshall runs in O(V^3) time and O(V^2) memory and accepts negative edges. A negative cycle shows up as d[i][i] < 0 for a vertex i on it. Be careful there: with a negative cycle the entries do not stop at a small negative number. On a complete graph where every weight is -1, self-loops included, the smallest entry after the three loops is about -2.0*10^7 for 10 vertices and -1.2*10^15 for 20 (we computed this in double to see it), so with long long the values overflow soon after. If negative cycles are possible, clamp updates at -kInf or stop as soon as some d[i][i] turns negative.

Counting the cost on the same graphs

The table at the top promised different growth rates. This program builds random graphs with E = 4V and counts the work each algorithm does: for Dijkstra, edge checks plus heap pushes and pops; for Bellman-Ford, edge checks over all V - 1 rounds; for Floyd-Warshall, executions of the innermost statement.

main.cppc++23

#include <algorithm>
#include <cstdint>
#include <functional>
#include <limits>
#include <print>
#include <queue>
#include <utility>
#include <vector>

using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;
struct Arc { int from, to; ll w; };
struct Lcg {
    std::uint64_t s;
    std::uint32_t next() {
        s = s * 6364136223846793005ULL + 1442695040888963407ULL;
        return std::uint32_t(s >> 33);
    }
    int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};

long dijkstraSteps(int n, const std::vector<Arc>& arcs) {
    std::vector<std::vector<std::pair<int, ll>>> g(n);
    for (auto [u, v, w] : arcs) g[u].push_back({v, w});
    std::vector<ll> d(n, kInf);
    std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>,
                        std::greater<>> pq;
    pq.push({d[0] = 0, 0});
    long steps = 0;  // edge checks + heap operations
    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        ++steps;
        if (du != d[u]) continue;
        for (auto [v, w] : g[u]) {
            ++steps;
            if (du + w < d[v]) pq.push({d[v] = du + w, v}), ++steps;
        }
    }
    return steps;
}

long bellmanFordSteps(int n, const std::vector<Arc>& arcs) {
    std::vector<ll> d(n, kInf);
    d[0] = 0;
    long steps = 0;  // edge checks, all n - 1 rounds (the worst case)
    for (int r = 1; r < n; ++r)
        for (auto [u, v, w] : arcs) {
            ++steps;
            if (d[u] != kInf) d[v] = std::min(d[v], d[u] + w);
        }
    return steps;
}

long floydSteps(int n, const std::vector<Arc>& arcs) {
    std::vector d(n, std::vector<ll>(n, kInf));
    for (int i = 0; i < n; ++i) d[i][i] = 0;
    for (auto [u, v, w] : arcs) d[u][v] = std::min(d[u][v], w);
    long steps = 0;  // executions of the innermost statement
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) {
                ++steps;
                if (d[i][k] < kInf && d[k][j] < kInf)
                    d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
            }
    return steps;
}

int main() {
    Lcg rng{7};
    std::println("{:>5} {:>6} {:>10} {:>12} {:>12}", "V", "E", "dijkstra",
                 "bellman-ford", "floyd");
    for (int n = 50; n <= 400; n *= 2) {
        std::vector<Arc> arcs;
        for (int i = 0; i < 4 * n; ++i)
            arcs.push_back({rng.range(0, n - 1), rng.range(0, n - 1),
                            rng.range(1, 100)});
        std::println("{:>5} {:>6} {:>10} {:>12} {:>12}", n, arcs.size(),
                     dijkstraSteps(n, arcs), bellmanFordSteps(n, arcs),
                     floydSteps(n, arcs));
    }
}

Output

Press Run to compile and run this example.

    V      E   dijkstra bellman-ford        floyd
   50    200        319         9800       125000
  100    400        637        39600      1000000
  200    800       1286       159200      8000000
  400   1600       2561       638400     64000000

Each doubling of V doubles Dijkstra's count (its log V factor lives inside each heap operation, which is counted as one step here), multiplies Bellman-Ford's by about four (V * E with E = 4V), and multiplies Floyd-Warshall's by eight. At V = 400 the three are four orders of magnitude apart. Put V = 2*10^5 into the same formulas and only Dijkstra is still usable.

Graphs: BFS, DFS, Connected Components and Topological Sort

Union-Find and Minimum Spanning Trees