The workhorse for single-source shortest path with non-negative weights.Analogy: Imagine a fire starting at the source node and spreading through the graph. The fire reaches closer nodes first, then spreads to farther ones. The priority queue ensures we always process the closest unvisited node, just like fire always advances through the shortest fuel path first.Why it works: Dijkstra greedily finalizes the closest unvisited node. With non-negative weights, once a node is finalized, no future path through unvisited nodes could be shorter (they would have to pass through nodes that are farther away and add non-negative weight). This greedy property breaks with negative weights.
Handles negative edge weights and detects negative cycles.Why Dijkstra Fails with Negative Weights: Dijkstra assumes once a node is “finalized,” its distance can’t improve. With negative edges, this breaks—a longer path might become shorter later!The Insight: After at most (n-1) relaxations of all edges, shortest paths are found (if no negative cycle). Why n-1? The longest simple path has n-1 edges.Negative Cycle Detection: If any distance improves on the nth iteration, there’s a negative cycle—distances can decrease infinitely!When to Use:
Negative edge weights (Dijkstra fails)
Need to detect negative cycles
Sparse graphs with few edges
const long long INF = 1e18;pair<vector<long long>, bool> bellmanFord( int start, int n, vector<tuple<int, int, int>>& edges) { vector<long long> dist(n + 1, INF); dist[start] = 0; // Relax all edges n-1 times for (int i = 0; i < n - 1; i++) { bool updated = false; for (auto [u, v, w] : edges) { if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; updated = true; } } if (!updated) break; // Early termination } // Check for negative cycle bool hasNegativeCycle = false; for (auto [u, v, w] : edges) { if (dist[u] != INF && dist[u] + w < dist[v]) { hasNegativeCycle = true; break; } } return {dist, hasNegativeCycle};}
Computes all-pairs shortest paths. Works with negative weights (but no negative cycles).The Idea: For each pair (i, j), try using each vertex k as an intermediate point.
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])Why the loop order matters: We iterate k on the outside. After iteration k, dist[i][j] contains the shortest path using only vertices 1 to k as intermediates.Complexity: O(V³)—only use when V ≤ 400When to Use:
Need all pairs shortest paths
Graph is dense (many edges)
V is small (≤ 400)
const long long INF = 1e18;vector<vector<long long>> floydWarshall(int n, vector<tuple<int, int, int>>& edges) { vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF)); // Initialize for (int i = 1; i <= n; i++) dist[i][i] = 0; for (auto [u, v, w] : edges) { dist[u][v] = min(dist[u][v], (long long)w); } // Floyd-Warshall for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][k] != INF && dist[k][j] != INF) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } return dist;}
Shortest Path Faster Algorithm—optimized Bellman-Ford with queue.
vector<long long> spfa(int start, vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<long long> dist(n, INF); vector<bool> inQueue(n, false); queue<int> q; dist[start] = 0; q.push(start); inQueue[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for (auto [v, w] : adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!inQueue[v]) { q.push(v); inQueue[v] = true; } } } } return dist;}
SPFA has worst-case O(VE) and can be slow on adversarial inputs. Many competitive programming judges include anti-SPFA test cases specifically to fail this algorithm. Prefer Dijkstra for non-negative weights. Only use SPFA when you need Bellman-Ford’s capabilities (negative weights) with potentially faster average performance.
Mistake 1: Wrong INF value
Use 1e18 for long long. Using INT_MAX causes overflow when adding: INT_MAX + 1 wraps to a negative number, which then appears “shorter” than real distances.
// WRONG -- overflow when checking dist[u] + wconst int INF = INT_MAX;// CORRECT -- large enough that INF + max_edge never overflows long longconst long long INF = 1e18;
Mistake 2: Not handling disconnected components
If destination is unreachable, return -1, not INF. Many problems penalize printing a huge number instead of -1 or “impossible.”
Mistake 3: Using Dijkstra with negative weights
Dijkstra does NOT work with negative edges. Use Bellman-Ford or SPFA. Even a single negative edge can make Dijkstra produce wrong answers, because it finalizes nodes greedily under the assumption that distances only increase.
Mistake 4: Multiple edges between the same pair of nodes
When reading the graph, always take the minimum weight if there are parallel edges:
adj[u][v] = min(adj[u][v], w); // For adjacency matrix// For adjacency list, it is fine to store all edges -- Dijkstra handles it
