Shortest Paths
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Algorithms and when to use them
BFS: unweighted/equal-weight edges.
0–1 BFS: edge weights are only 0 or 1.
Dijkstra: non-negative edge weights.
Bellman–Ford: supports negative edges and detects reachable negative cycles.
Floyd–Warshall: all-pairs shortest paths, typically O(V³) time and O(V²) memory.
DAG shortest paths: topological order, including negative edge weights.
Johnson's algorithm: sparse all-pairs setting with suitable reweighting.
A\*: heuristic-guided search, with admissibility/consistency conditions.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Three independent algorithms agree on the non-negative graph, and the stress test compares Dijkstra with Bellman–Ford on 300 random graphs. The next program shows what goes wrong once an edge is negative.
Dijkstra pops and finalises vertices 1, 3 and 4 (distances 1, 2, 3) before it pops vertex 2 at distance 4. Only then does it see the edge 2 → 1 of weight −4, which makes the route 0 → 2 → 1 cost 0 — but vertex 1 is already final, so the improvement is never propagated to 3 and 4. Bellman–Ford finds 0, 1 and 2 for vertices 1, 3 and 4. The greedy assumption “the closest unfinished vertex is final” needs non-negative weights.
Output (CPython 3.13.1): Same distances as the C++ run. Python's float("inf") is a convenient sentinel because it never overflows.
#include <bits/stdc++.h>
using namespace std;
const long long INF = LLONG_MAX / 4; // sentinel; INF + w cannot overflow
vector<long long> dijkstra(int V, const vector<vector<pair<int, int>>>& adj, int s) {
vector<long long> d(V, INF); d[s] = 0;
using T = pair<long long, int>;
priority_queue<T, vector<T>, greater<T>> pq; pq.push({0, s});
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != d[u]) continue; // stale entry (lazy deletion)
for (auto [v, w] : adj[u]) if (d[u] + w < d[v]) { d[v] = d[u] + w; pq.push({d[v], v}); }
}
return d;
}
// returns false if a negative cycle is reachable from s
bool bellmanFord(int V, const vector<tuple<int, int, int>>& edges, int s, vector<long long>& d) {
d.assign(V, INF); d[s] = 0;
for (int i = 0; i < V - 1; ++i)
for (auto [u, v, w] : edges) if (d[u] != INF && d[u] + w < d[v]) d[v] = d[u] + w;
for (auto [u, v, w] : edges) if (d[u] != INF && d[u] + w < d[v]) return false; // still improving
return true;
}
vector<vector<long long>> floyd(int V, const vector<tuple<int, int, int>>& edges) {
vector<vector<long lo
…Dijkstra from 0: 0 7 9 20 20 11
Bellman-Ford agrees: true, Floyd-Warshall row 0 agrees: true
negative cycle 1->2->1 (total -1): Bellman-Ford ok = false
unreachable vertex distance stays INF: true
Dijkstra matches Bellman-Ford on 300 random non-negative graphs#include <bits/stdc++.h>
using namespace std;
int main() {
// 0->1 (1), 0->2 (4), 1->3 (1), 3->4 (1), 2->1 (-4)
int V = 5;
vector<vector<pair<int, int>>> adj(V);
vector<tuple<int, int, int>> edges = {{0, 1, 1}, {0, 2, 4}, {1, 3, 1}, {3, 4, 1}, {2, 1, -4}};
for (auto [u, v, w] : edges) adj[u].push_back({v, w});
vector<long long> d(V, LLONG_MAX / 4); d[0] = 0;
using T = pair<long long, int>;
priority_queue<T, vector<T>, greater<T>> pq; pq.push({0, 0});
vector<bool> done(V, false);
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (done[u]) continue;
done[u] = true; // textbook Dijkstra: u is final once popped
for (auto [v, w] : adj[u]) if (!done[v] && d[u] + w < d[v]) { d[v] = d[u] + w; pq.push({d[v], v}); }
}
vector<long long> bf(V, LLONG_MAX / 4); bf[0] = 0;
for (int i = 0; i < V - 1; ++i) for (auto [u, v, w] : edges) if (bf[u] + w < bf[v]) bf[v] = bf[u] + w;
cout << "vertex: 0 1 2 3 4\nDijkstra: ";
for (long long x : d) cout << ' ' << x;
cout << "\nBellman-Ford: ";
for (long long x : bf) cout << ' ' << x;
cout << '\n';
…vertex: 0 1 2 3 4
Dijkstra: 0 1 4 2 3
Bellman-Ford: 0 0 4 1 2import heapq
edges = [(0, 1, 7), (0, 2, 9), (0, 5, 14), (1, 2, 10), (1, 3, 15), (2, 3, 11), (2, 5, 2), (3, 4, 6), (5, 4, 9)]
adj = [[] for _ in range(6)]
for u, v, w in edges:
adj[u].append((v, w))
INF = float("inf")
d = [INF] * 6
d[0] = 0
pq = [(0, 0)] # heapq is a min-heap of (distance, vertex)
while pq:
du, u = heapq.heappop(pq)
if du != d[u]:
continue # stale entry
for v, w in adj[u]:
if du + w < d[v]:
d[v] = du + w
heapq.heappush(pq, (d[v], v))
print("Dijkstra from 0:", d)Dijkstra from 0: [0, 7, 9, 20, 20, 11]Important caveats
Dijkstra is not correct with arbitrary negative edges. Distinguish unreachable nodes from large finite distances, guard overflow during addition, and explain negative-cycle effects.
Use a sentinel like LLONG_MAX / 4 so that INF + w cannot overflow, and test d[u] != INF before relaxing from u.
A reachable negative cycle makes shortest distances undefined (they go to −∞); Bellman–Ford reports it when a V-th round still improves something.
Complexities: Dijkstra with a binary heap O((V + E) log V); Bellman–Ford O(VE); Floyd–Warshall O(V³).
Quiz
? When is Dijkstra's algorithm guaranteed correct?
+ When every edge weight is non-negative :: The popped vertex is then final.
- Always :: The second program shows a wrong result with a negative edge.
- When the graph is a DAG :: A DAG still needs non-negative weights for Dijkstra (or use topological relaxation).
- When there are no cycles of length 2 :: Unrelated.
? Bellman–Ford detects a reachable negative cycle how?
+ A V-th pass over the edges still finds an improvement :: Simple paths need at most V−1 edges.
- Distances become negative :: Negative distances can be legitimate.
- It runs forever :: It stops after V passes.
- By using a heap :: No heap.
? Why use INF = LLONG_MAX / 4 rather than LLONG_MAX?
+ So INF + w does not overflow when relaxing from an unreached vertex :: Overflow is undefined behaviour.
- To save memory :: No.
- Because LLONG_MAX is negative :: It is positive.
- It is faster :: No.