Dijkstra's Algorithm: Shortest Paths Explained with Code

A map app finding the fastest route, a router choosing where to forward a packet, a game character walking round obstacles: each is a shortest path question on a weighted graph, where every edge has a cost and a path's length is the sum of its weights. Dijkstra's algorithm (1959) finds the shortest path from one source to every other vertex, as long as no weight is negative. After BFS and DFS it is the graph algorithm interviews ask about most.

1. BFS reaches vertices in order of how many edges away they are. C is one edge from A, so the first route BFS finds is A → C — and it costs 10.
2. Counting weight instead of edges, A → B → C costs 5, less than 10. Once edges have different weights, the route with fewest edges can be the expensive one — the gap Dijkstra's algorithm fills.

Why BFS is not enough

Breadth-First Search finds shortest paths only when every edge costs the same: it counts edges, not weight. Trying every route is hopeless: about 1.7 × 10¹⁶ simple paths join two vertices of a complete graph on 20. Bellman–Ford, later in this lesson, costs O(V × E): 2 × 10¹⁰ steps for V = 10⁵ and E = 2 × 10⁵. Dijkstra's algorithm needs about (V + E) log V, around 5 × 10⁶ steps, because it looks at each vertex's edges once.

The idea: settle the closest vertex first

Every vertex carries a tentative distance, the best route to it found so far: 0 for the source, ∞ for the rest. Then:

• Pick the unsettled vertex with the smallest tentative distance. Its distance is now final; the vertex is settled.
• Relax each of its edges u → v with weight w: if dist[u] + w < dist[v], going through u is shorter, so set dist[v] = dist[u] + w and remember prev[v] = u.
• Repeat until every reachable vertex is settled.

Picking the smallest distance quickly is a job for a min-heap — see the Heap lesson.

1. Each node carries a tentative distance from A: 0 for A itself, ∞ for the rest. Every step settles the unsettled node with the smallest one; with no negative weights, no path found later can undercut it.
2. Settle A at 0, the only finite distance left. Relaxing its edges: B gets 0 + 4 = 4; C gets 0 + 2 = 2.
3. Settle C at 2, the smallest unsettled distance (B 4, C 2). Relaxing its edges: B drops from 4 to 2 + 1 = 3; D gets 2 + 8 = 10; E gets 2 + 10 = 12. A path with more edges can still weigh less.
4. Settle B at 3, the smallest unsettled distance (B 3, D 10, E 12). Relaxing its edges: D drops from 10 to 3 + 5 = 8.
5. Settle D at 8, the smallest unsettled distance (D 8, E 12). Relaxing its edges: E drops from 12 to 8 + 2 = 10; F gets 8 + 3 = 11.
6. Settle E at 10, the smallest unsettled distance (E 10, F 11). Relaxing its edges: F would get 10 + 2 = 12, no better than 11, so it keeps 11.
7. Settle F at 11, the last node left. It has no edges to unsettled nodes, so nothing is relaxed, and every node is now settled.
8. Every distance is final: B 3, C 2, D 8, E 10, F 11. Following each node's last improving edge back gives the shortest path to F, A → C → B → D → F, cost 11. With a binary heap this is O((V + E) log V).

Why it works

The algorithm is greedy: it commits to a vertex's distance the moment that vertex is the closest unsettled one, and never revisits it. That is safe because any route it has not seen must leave the settled region somewhere, already at least as far as the vertex being settled, and the rest of the route can only add weight:

1. S = 0 and A = 2 are settled and final. Of the rest, U has the smallest tentative distance, 5, against Y's 7, so it is next. Could some route not yet seen reach U for less?
2. Any other route to U starts in the settled region and has to leave it somewhere. This one leaves on S → Y, arriving with at least d[Y] = 7 — and 7 ≥ 5, because U was the smallest.
3. The rest of the route, Y → U, can only add weight, because no weight is negative: 8 ≥ 5. Every route that leaves the region is at least as long, so 5 is final and U is settled for good.
4. That last step is the one a negative edge breaks. If Y → U weighed −3, the route through Y would cost 4, less than 5 — and U would already have been settled at the wrong distance.

Induction carries the argument from each settled vertex to the next, starting from the source at 0, so when the heap empties every reachable vertex holds its true distance.

Why a negative edge breaks it

The proof used non-negative weights exactly once. Take them away and a vertex can be settled before a cheaper route through a farther vertex is found:

1. Dijkstra from A on a graph with one negative edge, C → B weighing −2. The textbook algorithm settles the closest vertex and never looks at it again.
2. Settle A at 0 and relax its edges: B = 2 and C = 3.
3. B has the smallest distance, 2 (C has 3), so it is settled and final. Nothing that comes later is supposed to beat it.
4. Settle C at 3. Its edge to B gives 3 + (−2) = 1, less than 2 — but B is already settled, so the algorithm keeps 2. The true distance is 1: settling B first was wrong.

The lazy-heap code below would push B again and repair this small case, but the guarantee is gone: on bad graphs a vertex is reopened exponentially often, and a negative cycle — a loop of negative total weight — makes distances fall for ever. Use Bellman–Ford instead.

The code

The standard heaps have no "decrease key", so the code uses lazy deletion: when dist[v] improves it pushes a new entry and leaves the old one in place; a popped entry larger than dist[v] is stale and skipped. JavaScript has no heap in its standard library, so its program carries a small one.

#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

const string NAMES = "ABCDEF";
const int INF = INT_MAX;

// Dijkstra from source (all weights non-negative). Fills dist and prev
// (the vertex before each one on its shortest path) and returns the
// vertices in the order they were settled.
vector<int> dijkstra(const vector<vector<pair<int, int>>>& adj, int source, vector<int>& dist, vector<int>& prev) {
    int n = adj.size();
    dist.assign(n, INF);
    prev.assign(n, -1);
    vector<int> order;
    // std::priority_queue is a max-heap; greater<> turns it into a min-heap
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    dist[source] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (d > dist[u]) continue;          // stale: u was settled with a smaller distance
        order.push_back(u);                 // d is final: no later path can be shorter
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {          // relax the edge u -> v
                dist[v] = d + w;
                prev[v] = u;
                heap.push({dist[v], v});
            }
        }
    }
    return order;
}

int main() {
    int edges[][3] = {{0, 1, 4}, {0, 2, 2}, {2, 1, 1}, {1, 3, 5}, {2, 3, 8},
                      {2, 4, 10}, {3, 4, 2}, {3, 5, 3}, {4, 5, 2}};
    vector<vector<pair<int, int>>> adj(6);
    for (auto& e : edges) adj[e[0]].push_back({e[1], e[2]});
    vector<int> dist, prev;
    vector<int> order = dijkstra(adj, 0, dist, prev);

    cout << "Settled in order:";
    for (int v : order) cout << " " << NAMES[v];
    cout << "\nDistances from A:";
    for (int v = 0; v < 6; v++) cout << " " << NAMES[v] << "=" << dist[v];
    vector<int> path;
    for (int v = 5; v != -1; v = prev[v]) path.push_back(v);  // walk back from F
    reverse(path.begin(), path.end());
    cout << "\nPath to F:";
    for (size_t i = 0; i < path.size(); i++) cout << (i > 0 ? " -> " : " ") << NAMES[path[i]];
    cout << " (cost " << dist[5] << ")\n";
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static final String NAMES = "ABCDEF";
    static final int INF = Integer.MAX_VALUE;
    static int[] dist, prev;

    // Dijkstra from source (all weights non-negative). Fills dist and prev
    // (the vertex before each one on its shortest path) and returns the
    // vertices in the order they were settled.
    static List<Integer> dijkstra(List<List<int[]>> adj, int source) {
        int n = adj.size();
        dist = new int[n];
        prev = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        List<Integer> order = new ArrayList<>();
        // entries are {distance, vertex}: smallest distance first, then smallest vertex
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        dist[source] = 0;
        heap.add(new int[] {0, source});
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;          // stale: u was settled with a smaller distance
            order.add(u);                       // d is final: no later path can be shorter
            for (int[] e : adj.get(u)) {
                int v = e[0], w = e[1];
                if (d + w < dist[v]) {          // relax the edge u -> v
                    dist[v] = d + w;
                    prev[v] = u;
                    heap.add(new int[] {dist[v], v});
                }
            }
        }
        return order;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1, 4}, {0, 2, 2}, {2, 1, 1}, {1, 3, 5}, {2, 3, 8},
                         {2, 4, 10}, {3, 4, 2}, {3, 5, 3}, {4, 5, 2}};
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < 6; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]});
        List<Integer> order = dijkstra(adj, 0);

        StringBuilder out = new StringBuilder("Settled in order:");
        for (int v : order) out.append(" ").append(NAMES.charAt(v));
        out.append("\nDistances from A:");
        for (int v = 0; v < 6; v++) out.append(" ").append(NAMES.charAt(v)).append("=").append(dist[v]);
        List<Integer> path = new ArrayList<>();
        for (int v = 5; v != -1; v = prev[v]) path.add(v);      // walk back from F
        Collections.reverse(path);
        out.append("\nPath to F:");
        for (int i = 0; i < path.size(); i++) out.append(i > 0 ? " -> " : " ").append(NAMES.charAt(path.get(i)));
        out.append(" (cost ").append(dist[5]).append(")");
        System.out.println(out);
    }
}

import heapq

NAMES = "ABCDEF"
INF = float("inf")


def dijkstra(adj, source):
    """Dijkstra from source (all weights non-negative). Returns dist, prev
    (the vertex before each one on its shortest path) and the settle order."""
    n = len(adj)
    dist = [INF] * n
    prev = [-1] * n
    order = []
    heap = [(0, source)]  # (distance, vertex); heapq is a min-heap
    dist[source] = 0
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:  # stale: u was settled with a smaller distance
            continue
        order.append(u)  # d is final: no later path can be shorter
        for v, w in adj[u]:
            if d + w < dist[v]:  # relax the edge u -> v
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, prev, order


edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 5), (2, 3, 8),
         (2, 4, 10), (3, 4, 2), (3, 5, 3), (4, 5, 2)]
adj = [[] for _ in range(6)]
for u, v, w in edges:
    adj[u].append((v, w))
dist, prev, order = dijkstra(adj, 0)

print("Settled in order:", *(NAMES[v] for v in order))
print("Distances from A:", *(f"{NAMES[v]}={dist[v]}" for v in range(6)))
path = []
v = 5
while v != -1:  # walk back from F
    path.append(v)
    v = prev[v]
path.reverse()
print("Path to F:", " -> ".join(NAMES[v] for v in path), f"(cost {dist[5]})")

// JavaScript has no priority queue, so here is a small binary min-heap
// of [distance, vertex] pairs, ordered by distance, then by vertex.
class MinHeap {
  constructor() {
    this.items = [];
  }
  less(i, j) {
    const a = this.items[i], b = this.items[j];
    return a[0] !== b[0] ? a[0] < b[0] : a[1] < b[1];
  }
  swap(i, j) {
    [this.items[i], this.items[j]] = [this.items[j], this.items[i]];
  }
  push(item) {
    this.items.push(item);
    let i = this.items.length - 1;
    while (i > 0 && this.less(i, (i - 1) >> 1)) { // sift up past larger parents
      this.swap(i, (i - 1) >> 1);
      i = (i - 1) >> 1;
    }
  }
  pop() {
    const top = this.items[0];
    const last = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = last;
      let i = 0;
      for (;;) { // sift down towards the smaller child
        let m = i;
        for (const c of [2 * i + 1, 2 * i + 2]) if (c < this.items.length && this.less(c, m)) m = c;
        if (m === i) break;
        this.swap(i, m);
        i = m;
      }
    }
    return top;
  }
}

const NAMES = "ABCDEF";

// Dijkstra from source (all weights non-negative): dist, prev (the vertex
// before each one on its shortest path) and the settle order.
function dijkstra(adj, source) {
  const n = adj.length;
  const dist = new Array(n).fill(Infinity);
  const prev = new Array(n).fill(-1);
  const order = [];
  const heap = new MinHeap();
  dist[source] = 0;
  heap.push([0, source]);
  while (heap.items.length > 0) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue; // stale: u was settled with a smaller distance
    order.push(u); // d is final: no later path can be shorter
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) { // relax the edge u -> v
        dist[v] = d + w;
        prev[v] = u;
        heap.push([dist[v], v]);
      }
    }
  }
  return { dist, prev, order };
}

const edges = [[0, 1, 4], [0, 2, 2], [2, 1, 1], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2], [3, 5, 3], [4, 5, 2]];
const adj = Array.from({ length: 6 }, () => []);
for (const [u, v, w] of edges) adj[u].push([v, w]);
const { dist, prev, order } = dijkstra(adj, 0);

console.log(`Settled in order: ${order.map((v) => NAMES[v]).join(" ")}`);
console.log(`Distances from A: ${dist.map((d, v) => `${NAMES[v]}=${d}`).join(" ")}`);
const path = [];
for (let v = 5; v !== -1; v = prev[v]) path.push(v); // walk back from F
path.reverse();
console.log(`Path to F: ${path.map((v) => NAMES[v]).join(" -> ")} (cost ${dist[5]})`);

Settled in order: A C B D E F
Distances from A: A=0 B=3 C=2 D=8 E=10 F=11
Path to F: A -> C -> B -> D -> F (cost 11)

The program's heap, entry by entry — stale entries are greyed out while they wait:

1. dist starts at 0 for the source A and ∞ elsewhere, and the heap holds one entry, (distance, vertex) = (0, A). Each step pops the smallest entry.
2. Pop (0, A): 0 = dist[A], so A is settled. Relaxing its edges: B gets 4; C gets 2.
3. Pop (2, C): 2 = dist[C], so C is settled. Relaxing its edges: B drops from 4 to 3; D gets 10; E gets 12. B's old entry stays in the heap: finding and removing it would need a decrease-key that the standard heaps lack.
4. Pop (3, B): 3 = dist[B], so B is settled. Relaxing its edges: D drops from 10 to 8.
5. Pop (4, B), but dist[B] is already 3: this entry is stale, left over from before B improved. Skip it without touching a single edge.
6. Pop (8, D): 8 = dist[D], so D is settled. Relaxing its edges: E drops from 12 to 10; F gets 11.
7. Pop (10, D), but dist[D] is already 8: this entry is stale, left over from before D improved. Skip it without touching a single edge.
8. Pop (10, E): 10 = dist[E], so E is settled. Relaxing its edges: E → F would give 12, no better than 11.
9. Pop (11, F): 11 = dist[F], so F is settled. It has no edges to relax.
10. Pop (12, E): stale too, since dist[E] = 10. The heap is empty. Of 9 entries pushed, 3 were stale; the settling order was A, C, B, D, E, F — by distance, not by name.

Network Delay Time is this program almost unchanged: run it from the given node and answer with the largest distance, or −1 if any is still ∞.

Rebuilding the path

prev[v] changes only when dist[v] improves, so at the end it names the vertex whose relaxation set v's final distance — and that vertex was itself final by then. Following prev from any vertex therefore walks back to the source along a shortest path, and together the pointers form a shortest-path tree.

1. prev[v] is the vertex whose relaxation last improved v. Drawn as edges, the 5 prev pointers form a tree rooted at A — the shortest-path tree — and no faint edge lies on a shortest path from A.
2. To print the path to F, start there and follow prev until it runs out: F ← D ← B ← C ← A. Reversed, that is the route, cost 11. A vertex left at ∞ has no prev, so check the distance before walking.

Negative weights: Bellman–Ford

Bellman–Ford gives up the greedy choice: it relaxes every edge, in any order, and repeats that V − 1 times. That is enough because, without a negative cycle, a shortest path never repeats a vertex, so it has at most V − 1 edges — and after round k, every vertex whose shortest path has at most k edges holds its correct distance. It also gives the negative-cycle test: one more pass over the edges. If anything still improves, a negative cycle is reachable from the source and "shortest path" has no meaning.

1. Bellman–Ford relaxes every edge, in one fixed order, round after round: V − 1 = 4 rounds. The order below is the worst one for this graph — the shortest path to D uses these edges back to front.
2. Round 1: S → A gives A = 4 and S → B gives B = 5. No other edge starts from a known distance yet.
3. Round 2: A → C gives C = 7 and B → A gives A = 2. B → A, weighing −3, beats the direct edge: a route with more edges can be cheaper.
4. Round 3: C → D gives D = 9 and A → C gives C = 5.
5. Round 4: C → D gives D = 7. The shortest path S → B → A → C → D has 4 edges, and this order fixed one per round, so all 4 rounds were needed.
6. One extra pass over the edges improves nothing, so there is no negative cycle and every distance is final. The prev pointers give S → B → A → C → D, cost 7.
7. Now add C → B weighing −8: the loop B → A → C → B weighs −3 + 3 − 8 = −8. After 4 rounds the extra pass still improves 4 edges: a negative cycle is reachable, and going round it lowers every distance again, so no shortest path exists.

The program prints the distances after each round, then repeats the run with the extra edge C → B weighing −8.

#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const string NAMES = "SABCD";
const int INF = INT_MAX;

// Bellman-Ford from source; weights may be negative. Fills dist and prev and
// returns true when a negative cycle is reachable from the source.
bool bellmanFord(int n, const vector<vector<int>>& edges, int source, bool trace, vector<int>& dist, vector<int>& prev) {
    dist.assign(n, INF);
    prev.assign(n, -1);
    dist[source] = 0;
    for (int round = 1; round < n; round++) {          // V - 1 rounds are always enough
        for (const auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) {  // never add to infinity
                dist[v] = dist[u] + w;
                prev[v] = u;
            }
        }
        if (trace) {
            cout << "Round " << round << ":";
            for (int x = 0; x < n; x++) cout << " " << NAMES[x] << "=" << (dist[x] == INF ? string("inf") : to_string(dist[x]));
            cout << "\n";
        }
    }
    for (const auto& e : edges)                        // one more pass: any improvement means a negative cycle
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return true;
    return false;
}

int main() {
    vector<vector<int>> edges = {{3, 4, 2}, {1, 3, 3}, {2, 3, 4}, {2, 1, -3}, {0, 1, 4}, {0, 2, 5}};
    vector<int> dist, prev;
    bellmanFord(5, edges, 0, true, dist, prev);
    vector<int> path;
    for (int v = 4; v != -1; v = prev[v]) path.push_back(v);  // walk back from D
    reverse(path.begin(), path.end());
    cout << "Path to D:";
    for (size_t i = 0; i < path.size(); i++) cout << (i > 0 ? " -> " : " ") << NAMES[path[i]];
    cout << " (cost " << dist[4] << ")\n";

    edges.push_back({3, 2, -8});                       // C -> B closes B -> A -> C -> B, total -8
    bool cycle = bellmanFord(5, edges, 0, false, dist, prev);
    cout << "With C -> B weighing -8: " << (cycle ? "negative cycle reachable from S" : "no negative cycle") << "\n";
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    static final String NAMES = "SABCD";
    static final int INF = Integer.MAX_VALUE;
    static int[] dist, prev;

    // Bellman-Ford from source; weights may be negative. Fills dist and prev and
    // returns true when a negative cycle is reachable from the source.
    static boolean bellmanFord(int n, List<int[]> edges, int source, boolean trace) {
        dist = new int[n];
        prev = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[source] = 0;
        for (int round = 1; round < n; round++) {          // V - 1 rounds are always enough
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != INF && dist[u] + w < dist[v]) {  // never add to infinity
                    dist[v] = dist[u] + w;
                    prev[v] = u;
                }
            }
            if (trace) {
                StringBuilder line = new StringBuilder("Round " + round + ":");
                for (int x = 0; x < n; x++) line.append(" ").append(NAMES.charAt(x)).append("=").append(dist[x] == INF ? "inf" : String.valueOf(dist[x]));
                System.out.println(line);
            }
        }
        for (int[] e : edges)                              // one more pass: any improvement means a negative cycle
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return true;
        return false;
    }

    public static void main(String[] args) {
        List<int[]> edges = new ArrayList<>(Arrays.asList(
            new int[] {3, 4, 2}, new int[] {1, 3, 3}, new int[] {2, 3, 4},
            new int[] {2, 1, -3}, new int[] {0, 1, 4}, new int[] {0, 2, 5}));
        bellmanFord(5, edges, 0, true);
        List<Integer> path = new ArrayList<>();
        for (int v = 4; v != -1; v = prev[v]) path.add(v);       // walk back from D
        Collections.reverse(path);
        StringBuilder line = new StringBuilder("Path to D:");
        for (int i = 0; i < path.size(); i++) line.append(i > 0 ? " -> " : " ").append(NAMES.charAt(path.get(i)));
        System.out.println(line + " (cost " + dist[4] + ")");

        edges.add(new int[] {3, 2, -8});                   // C -> B closes B -> A -> C -> B, total -8
        boolean cycle = bellmanFord(5, edges, 0, false);
        System.out.println("With C -> B weighing -8: " + (cycle ? "negative cycle reachable from S" : "no negative cycle"));
    }
}

NAMES = "SABCD"
INF = float("inf")


def bellman_ford(n, edges, source, trace):
    """Bellman-Ford from source; weights may be negative. Returns dist, prev
    and whether a negative cycle is reachable from the source."""
    dist = [INF] * n
    prev = [-1] * n
    dist[source] = 0
    for rnd in range(1, n):  # V - 1 rounds are always enough
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:  # never add to infinity
                dist[v] = dist[u] + w
                prev[v] = u
        if trace:
            shown = ("inf" if d == INF else str(d) for d in dist)
            print(f"Round {rnd}:", *(f"{NAMES[x]}={s}" for x, s in enumerate(shown)))
    for u, v, w in edges:  # one more pass: any improvement means a negative cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return dist, prev, True
    return dist, prev, False


edges = [(3, 4, 2), (1, 3, 3), (2, 3, 4), (2, 1, -3), (0, 1, 4), (0, 2, 5)]
dist, prev, _ = bellman_ford(5, edges, 0, True)
path = []
v = 4
while v != -1:  # walk back from D
    path.append(v)
    v = prev[v]
path.reverse()
print("Path to D:", " -> ".join(NAMES[v] for v in path), f"(cost {dist[4]})")

edges.append((3, 2, -8))  # C -> B closes B -> A -> C -> B, total -8
_, _, cycle = bellman_ford(5, edges, 0, False)
print("With C -> B weighing -8:", "negative cycle reachable from S" if cycle else "no negative cycle")

const NAMES = "SABCD";

// Bellman-Ford from source; weights may be negative. Returns dist, prev and
// whether a negative cycle is reachable from the source.
function bellmanFord(n, edges, source, trace) {
  const dist = new Array(n).fill(Infinity);
  const prev = new Array(n).fill(-1);
  dist[source] = 0;
  for (let round = 1; round < n; round++) { // V - 1 rounds are always enough
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) { // never add to infinity
        dist[v] = dist[u] + w;
        prev[v] = u;
      }
    }
    if (trace) {
      const shown = dist.map((d, x) => `${NAMES[x]}=${d === Infinity ? "inf" : d}`);
      console.log(`Round ${round}: ${shown.join(" ")}`);
    }
  }
  for (const [u, v, w] of edges) { // one more pass: any improvement means a negative cycle
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) return { dist, prev, cycle: true };
  }
  return { dist, prev, cycle: false };
}

const edges = [[3, 4, 2], [1, 3, 3], [2, 3, 4], [2, 1, -3], [0, 1, 4], [0, 2, 5]];
const { dist, prev } = bellmanFord(5, edges, 0, true);
const path = [];
for (let v = 4; v !== -1; v = prev[v]) path.push(v); // walk back from D
path.reverse();
console.log(`Path to D: ${path.map((v) => NAMES[v]).join(" -> ")} (cost ${dist[4]})`);

edges.push([3, 2, -8]); // C -> B closes B -> A -> C -> B, total -8
const { cycle } = bellmanFord(5, edges, 0, false);
console.log(`With C -> B weighing -8: ${cycle ? "negative cycle reachable from S" : "no negative cycle"}`);

Round 1: S=0 A=4 B=5 C=inf D=inf
Round 2: S=0 A=2 B=5 C=7 D=inf
Round 3: S=0 A=2 B=5 C=5 D=9
Round 4: S=0 A=2 B=5 C=5 D=7
Path to D: S -> B -> A -> C -> D (cost 7)
With C -> B weighing -8: negative cycle reachable from S

The dist[u] != INF test matters in C++ and Java: adding a weight to INT_MAX overflows into a large negative number, which would look like a wonderful shortcut. Stopping early when a whole round changes nothing gives the same answer and finishes sparse inputs much sooner.

Other shapes of the same idea

• 0-1 BFS: with weights of only 0 and 1, a deque replaces the heap — 0-edges to the front, 1-edges to the back — and stays sorted in O(V + E), as in Minimum Obstacle Removal to Reach Corner.
• Grids: each cell is a vertex; in The Maze II each roll is one edge weighted by the cells it crosses.
• Minimax paths: when a route costs its largest step, as in Path With Minimum Effort, relax with max(dist[u], w). A route's cost still never falls as it grows, the property the proof really needs.
• Counting shortest paths: keep ways[v] beside dist[v]; a strictly shorter distance copies ways[u], an equal one adds it.
• At most k edges: Cheapest Flights Within K Stops runs k + 1 Bellman–Ford rounds, each relaxing from a copy of the previous round.
• All pairs: Dijkstra from every vertex, or Floyd–Warshall in O(V³).

Time and space complexity

Each edge pushes at most one heap entry, and each push or pop costs O(log E), under 2 log V. Scanning an array instead of a heap costs O(V²), better when E is close to V².

How to recognise a shortest-path problem

• It asks for the minimum time, cost, distance or effort to get from one place to another, and moves have different costs.
• It asks how long until something reaches every node: the largest shortest distance.
• The costs pick the algorithm: all equal means BFS, only 0 and 1 means 0-1 BFS, non-negative means Dijkstra, possibly negative means Bellman–Ford.
• There is an extra limit, such as at most k stops: count rounds with Bellman–Ford or put the count in the state.

Connecting everything at the lowest total cost is a different problem, the minimum spanning tree.

Common mistakes

• Negative weights. Dijkstra's algorithm silently gives wrong answers, or never stops on a negative cycle. Check the constraints first.
• Marking vertices when pushed instead of when popped. A vertex is final only when it comes off the heap.
• A max-heap by accident. std::priority_queue is a max-heap; use greater<> or push negated distances. Java's PriorityQueue and Python's heapq are min-heaps.
• Overflow. INT_MAX + w wraps round to a negative number; relax only from finite distances.
• Forgetting the reverse edge. In an undirected graph, add every edge in both directions.

Practice in this order

1. Network Delay Time: the algorithm unchanged; answer with the largest distance.
2. Path With Minimum Effort: the minimax relaxation on a grid.
3. The Maze II: rolls as weighted edges.
4. Cheapest Flights Within K Stops: Bellman–Ford rounds over a copy.
5. Find the City With the Smallest Number of Neighbors at a Threshold Distance: distances between all pairs.
6. Number of Ways to Arrive at Destination: count shortest paths alongside the distances.
7. Minimum Obstacle Removal to Reach Corner: 0-1 BFS.
8. Swim in Rising Water: the minimax idea on heights.
9. Minimum Cost to Make at Least One Valid Path in a Grid: 0-1 BFS where an edge's cost depends on a sign.

The shortest path problem list has every problem in the catalogue that uses these algorithms. Next on the road is the Minimum Spanning Tree, which connects every vertex as cheaply as possible.