What is the brute force approach and complexity for Dijkstra's Algorithm (template)?

Relax every edge in both directions, V − 1 times with time complexity O(V · E) and space complexity O(V).

What is the optimal approach and complexity for Dijkstra's Algorithm (template)?

Pop the closest tentative node from a min-heap; skip stale entries with optimal time complexity O((V + E) log V) and space complexity O(V + E).

How do you identify the pattern for Dijkstra's Algorithm (template)?

Look for key signals in the prompt: "shortest distance from src to every node" indicates One source and a distance for every node: Dijkstra, returning the whole array.; "weighted edges" indicates Plain BFS counts edges, not cost. Use a priority queue ordered by cost.; "w ≥ 0" indicates Non-negative weights are what make the closest unfinished node final..

Dijkstra's Algorithm (template)

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelShortest Paths (Dijkstra): min-heap with lazy deletion

Complexity:O(V · E)→O((V + E) log V)

Key Insight

Keep a min-heap of (distance, node). Pop the smallest entry. If it is stale (its distance is bigger than dist[u]), skip it. Otherwise u is settled: relax its edges and push every neighbour that improved. Never change an entry inside the heap; push a new one instead.

Core Validity Invariant

A popped entry is live when its distance equals dist[u]. A live node is final, because every unfinished route must leave through a heap entry at least as far away.

Problem

You are given V nodes numbered 0 to V − 1 and a list of undirected weighted edges. Each edge [u, v, w] joins u and v, and crossing it in either direction takes w time, with w ≥ 0. You are also given a source node src.

Return the shortest distance from src to every node as one array: entry i is the distance to node i. If a node cannot be reached, its entry is INT_MAX.

Write vector<int> dijkstra(int V, vector<vector<int>>& edges, int src) inside class Solution.

Input

V, the number of nodes. edges, a list of [u, v, w]. src, the start node.

Output

A list of V integers: the shortest distance from src to each node, or INT_MAX for a node that cannot be reached.

Example 1

Input: V = 6, src = 0, edges = [[3,4,3],[2,4,8],[1,3,1],[2,3,5],[2,1,2],[0,2,1],[0,1,4]]

Output: [0, 3, 1, 4, 7, INT_MAX]

Node 1 is 4 away by its direct edge, but 0 → 2 → 1 costs 1 + 2 = 3, so 3 wins. Node 5 has no edges, so it stays INT_MAX.

Example 2

Input: V = 3, src = 2, edges = [[0,1,5]]

Output: [INT_MAX, INT_MAX, 0]

The only edge does not touch the source, so only node 2 (the source itself) is at distance 0.

Constraints

• Nodes are numbered 0 to V − 1, and `src` is one of them.
• Every weight is 0 or more. Dijkstra needs non-negative weights.
• The graph is undirected: an edge can be used in both directions.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The question says shortest. Does it mean the fewest edges, or the least total weight?
2.
If the closest unfinished node is at distance 4 right now, can a longer route still reach it sooner?
3.
BFS handles the fewest-steps question. What breaks when one edge costs 1 and another costs 8?
4.
A node can be reached in two ways with two different distances. Which one do I keep, and what happens to the other?
5.
How many heap pushes can one edge cause at most?

Brute force approach

Idea

Start with dist[src] = 0 and INT_MAX everywhere else. Then go through every edge in both directions, and whenever dist[u] + w < dist[v], update dist[v]. Do this for V − 1 full rounds. There is no order to follow and no heap.

Thinking process

1
A shortest route never needs more than V − 1 edges, because a route through V nodes has at most V − 1 links.
2
One full round lets every route grow by one more edge. After V − 1 rounds, every route has had enough room.
3
On the dry run, round 1 sets node 1 to 4 (the direct edge from 0) and node 2 to 1. Round 2 finds 0 → 2 → 1 = 3 and lowers node 1 to 3.
4
Read the array after the last round. Each entry is the smallest value any round found for that node.

Visual

Each round relaxes every edge in both directions, in the input order. Green = distance improved this round, blue edge = the improving edge. Node 5 never changes.

Bellman-Ford: V - 1 rounds over every edgeV = 6, src = 0, edges (u, v, w) = [3,4,3], [2,4,8], [1,3,1], [2,3,5], [2,1,2], [0,2,1], [0,1,4]step 1/7

undirected weighted graph

dist

∞

State

round: 0 (start)
rounds to go: 5

Only the source has a known distance

Brute force: there is no order to follow, so keep relaxing every edge. A shortest route uses at most V - 1 = 5 edges, so 5 full rounds are enough. Each edge is tried in both directions.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> dijkstra(int V, vector<vector<int>>& edges, int src) {
        vector<int> dist(V, INT_MAX);   // INT_MAX = not reached yet
        dist[src] = 0;

        // Relax one undirected edge, in both directions.
        auto relax = [&](int u, int v, int w) {
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        };

        // A shortest path never needs more than V - 1 edges, so after V - 1 full
        // rounds every node has seen its best route. Each round looks at every edge.
        for (int round = 0; round < V - 1; round++)
            for (auto& e : edges) {
                relax(e[0], e[1], e[2]);
                relax(e[1], e[0], e[2]);
            }
        return dist;
    }
};

import java.util.*;

class Solution {
    public int[] dijkstra(int V, int[][] edges, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);   // Integer.MAX_VALUE = not reached yet
        dist[src] = 0;

        // A shortest path never needs more than V - 1 edges, so after V - 1 full
        // rounds every node has seen its best route. Each round looks at every edge.
        for (int round = 0; round < V - 1; round++) {
            for (int[] e : edges) {
                relax(dist, e[0], e[1], e[2]);
                relax(dist, e[1], e[0], e[2]);
            }
        }
        return dist;
    }

    // Relax one undirected edge, in both directions.
    private void relax(int[] dist, int u, int v, int w) {
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
        }
    }
}

from typing import List

class Solution:
    def dijkstra(self, V: int, edges: List[List[int]], src: int) -> List[int]:
        INT_MAX = 2147483647
        dist = [INT_MAX] * V   # INT_MAX = not reached yet
        dist[src] = 0

        # Relax one undirected edge, in both directions.
        def relax(u: int, v: int, w: int) -> None:
            if dist[u] != INT_MAX and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

        # A shortest path never needs more than V - 1 edges, so after V - 1 full
        # rounds every node has seen its best route. Each round looks at every edge.
        for _ in range(V - 1):
            for e in edges:
                relax(e[0], e[1], e[2])
                relax(e[1], e[0], e[2])

        return dist

export function dijkstra(V: number, edges: number[][], src: number): number[] {
    const INT_MAX = 2147483647;
    const dist: number[] = new Array(V).fill(INT_MAX);   // INT_MAX = not reached yet
    dist[src] = 0;

    // Relax one undirected edge, in both directions.
    const relax = (u: number, v: number, w: number): void => {
        if (dist[u] !== INT_MAX && dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
        }
    };

    // A shortest path never needs more than V - 1 edges, so after V - 1 full
    // rounds every node has seen its best route. Each round looks at every edge.
    for (let round = 0; round < V - 1; round++) {
        for (const e of edges) {
            relax(e[0], e[1], e[2]);
            relax(e[1], e[0], e[2]);
        }
    }
    return dist;
}

Complexity

Time O(V · E)Space O(V)

There are V − 1 rounds, and each round checks all E edges in both directions, so about 2 · V · E checks. The brute always runs every round, even when an earlier round changed nothing. Here V is the number of nodes and E the number of edges.

Better approach

Why brute force is slow

Bellman-Ford runs V − 1 full rounds over all edges. After the first few rounds almost every distance is final, yet every edge is still read again.

What repeated work are we doing?

An edge is checked again in every round, even when its start node has not changed since the round before.

What information can we reuse?

The closest unsettled node is final, because no weight is negative. So settle nodes in order of distance, once each. Each node relaxes its edges one time, so every edge is checked once.

New approach

Idea

Settle nodes one at a time. Each time, scan all nodes for the closest one that is not settled yet and has a finite distance. Mark it settled, then relax its edges once. No heap is needed.

Thinking process

1
Bellman-Ford wastes work: it re-reads every edge in every round, even edges whose start node was final rounds ago.
2
Dijkstra's fact: the unsettled node with the smallest distance is final. So each node only has to be handled once, at the moment it is picked.
3
Picking the closest node by a linear scan costs V steps, and V picks make about V² steps in total.
4
On the dry run: pick node 0 (distance 0) and relax to 2 (1) and 1 (4). Pick node 2 (1) and relax to 1 (3), 3 (6) and 4 (9). Node 1 is now 3, not 4.

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> dijkstra(int V, vector<vector<int>>& edges, int src) {
        // adj[u] = {v, w} for every edge, stored in both directions.
        vector<vector<pair<int, int>>> adj(V);
        for (auto& e : edges) {
            adj[e[0]].push_back({e[1], e[2]});
            adj[e[1]].push_back({e[0], e[2]});
        }

        vector<int> dist(V, INT_MAX);
        vector<bool> settled(V, false);
        dist[src] = 0;

        for (int step = 0; step < V; step++) {
            // Scan every node for the closest unsettled one (no heap).
            int u = -1;
            for (int i = 0; i < V; i++)
                if (!settled[i] && dist[i] != INT_MAX && (u == -1 || dist[i] < dist[u])) u = i;
            if (u == -1) break;        // what is left cannot be reached

            settled[u] = true;         // dist[u] is final: no later route can beat it
            for (auto [v, w] : adj[u])
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
        return dist;
    }
};

import java.util.*;

class Solution {
    public int[] dijkstra(int V, int[][] edges, int src) {
        // adj[u] = {v, w} for every edge, stored in both directions.
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});
        }

        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] settled = new boolean[V];
        dist[src] = 0;

        for (int step = 0; step < V; step++) {
            // Scan every node for the closest unsettled one (no heap).
            int u = -1;
            for (int i = 0; i < V; i++) {
                if (!settled[i] && dist[i] != Integer.MAX_VALUE && (u == -1 || dist[i] < dist[u])) {
                    u = i;
                }
            }
            if (u == -1) break;        // what is left cannot be reached

            settled[u] = true;         // dist[u] is final: no later route can beat it
            for (int[] edge : adj.get(u)) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        return dist;
    }
}

from typing import List, Tuple

class Solution:
    def dijkstra(self, V: int, edges: List[List[int]], src: int) -> List[int]:
        # adj[u] = {v, w} for every edge, stored in both directions.
        adj: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
        for e in edges:
            adj[e[0]].append((e[1], e[2]))
            adj[e[1]].append((e[0], e[2]))

        INT_MAX = 2147483647
        dist = [INT_MAX] * V
        settled = [False] * V
        dist[src] = 0

        for _ in range(V):
            # Scan every node for the closest unsettled one (no heap).
            u = -1
            for i in range(V):
                if not settled[i] and dist[i] != INT_MAX and (u == -1 or dist[i] < dist[u]):
                    u = i
            if u == -1:
                break        # what is left cannot be reached

            settled[u] = True         # dist[u] is final: no later route can beat it
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        return dist

export function dijkstra(V: number, edges: number[][], src: number): number[] {
    // adj[u] = {v, w} for every edge, stored in both directions.
    const adj: [number, number][][] = Array.from({ length: V }, () => []);
    for (const e of edges) {
        adj[e[0]].push([e[1], e[2]]);
        adj[e[1]].push([e[0], e[2]]);
    }

    const INT_MAX = 2147483647;
    const dist: number[] = new Array(V).fill(INT_MAX);
    const settled: boolean[] = new Array(V).fill(false);
    dist[src] = 0;

    for (let step = 0; step < V; step++) {
        // Scan every node for the closest unsettled one (no heap).
        let u = -1;
        for (let i = 0; i < V; i++) {
            if (!settled[i] && dist[i] !== INT_MAX && (u === -1 || dist[i] < dist[u])) {
                u = i;
            }
        }
        if (u === -1) break;        // what is left cannot be reached

        settled[u] = true;         // dist[u] is final: no later route can beat it
        for (const [v, w] of adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    return dist;
}

Complexity

Time O(V² + E)Space O(V + E)

V picks, each scanning V nodes, give V² work. The relaxations add E in total. For a dense graph, where E is close to V², this is as good as the heap version and simpler to write. The adjacency lists cost O(V + E) space.

Optimized approach

Idea

Start from brute force

Bellman-Ford tries every edge in every round. Dijkstra uses the fact that the closest unsettled node is final, so each node is handled once, in order of distance.

Find the repeated work

The array version still scans all V nodes to find the closest unsettled node. The heap keeps the candidates sorted, so that search costs O(log V) instead.

Define the state — what variables do I need?

dist[v]: The shortest distance found so far to node v. `INT_MAX` means not reached yet.
pq: Min-heap of (distance, node) pairs. An entry is **live** only if its distance equals dist[node].

Define validity

A popped entry is live when its distance equals dist[u]. A live node is final, because every unfinished route must leave through a heap entry at least as far away.

Define the transitions — when does each pointer move, and why is it safe?

Start

dist[src] = 0, then push (0, src)

The source is at distance 0, and that is the only fact we know at the start.

Pop (d, u) with d > dist[u]

Skip the entry

Node u was already reached with a shorter distance, so this entry is stale.

Pop (d, u) with d = dist[u]

For each edge (u, v, w): if d + w < dist[v], set dist[v] = d + w and push (dist[v], v)

The route to v through u beats every route found so far, and u's distance is final, so the route is real.

What does the current window add to the answer?

When the heap is empty, every reachable node holds its final distance in dist. Unreached nodes keep INT_MAX.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> dijkstra(int V, vector<vector<int>>& edges, int src) {
        // adj[u] = {v, w} for every edge, stored in both directions.
        vector<vector<pair<int, int>>> adj(V);
        for (auto& e : edges) {
            adj[e[0]].push_back({e[1], e[2]});
            adj[e[1]].push_back({e[0], e[2]});
        }

        vector<int> dist(V, INT_MAX);   // INT_MAX = not reached yet
        // Min-heap of {distance, node}: the closest tentative node comes out first.
        priority_queue<pair<int, int>, vector<pair<int, int>>, 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 reached with a smaller distance

            for (auto [v, w] : adj[u])
                if (d + w < dist[v]) {   // a shorter way to v through u
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
        }
        return dist;
    }
};

import java.util.*;

class Solution {
    public int[] dijkstra(int V, int[][] edges, int src) {
        // adj[u] = {v, w} for every edge, stored in both directions.
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});
        }

        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);   // Integer.MAX_VALUE = not reached yet
        // Min-heap of {distance, node}: the closest tentative node comes out first.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        dist[src] = 0;
        pq.offer(new int[]{0, src});

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;   // stale entry: u was reached with a smaller distance

            for (int[] edge : adj.get(u)) {
                int v = edge[0], w = edge[1];
                if (d + w < dist[v]) {   // a shorter way to v through u
                    dist[v] = d + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

from typing import List, Tuple
import heapq

class Solution:
    def dijkstra(self, V: int, edges: List[List[int]], src: int) -> List[int]:
        # adj[u] = {v, w} for every edge, stored in both directions.
        adj: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
        for e in edges:
            adj[e[0]].append((e[1], e[2]))
            adj[e[1]].append((e[0], e[2]))

        INT_MAX = 2147483647
        dist = [INT_MAX] * V   # INT_MAX = not reached yet
        # Min-heap of {distance, node}: the closest tentative node comes out first.
        pq: List[Tuple[int, int]] = []
        dist[src] = 0
        heapq.heappush(pq, (0, src))

        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue   # stale entry: u was reached with a smaller distance

            for v, w in adj[u]:
                if d + w < dist[v]:   # a shorter way to v through u
                    dist[v] = d + w
                    heapq.heappush(pq, (dist[v], v))

        return dist

class MinHeap<T> {
    private data: T[] = [];
    constructor(private compare: (a: T, b: T) => number) {}

    push(val: T): void {
        this.data.push(val);
        this.bubbleUp(this.data.length - 1);
    }

    pop(): T | undefined {
        if (this.data.length === 0) return undefined;
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return top;
    }

    size(): number {
        return this.data.length;
    }

    isEmpty(): boolean {
        return this.data.length === 0;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.compare(this.data[idx], this.data[parent]) < 0) {
                [this.data[idx], this.data[parent]] = [this.data[parent], this.data[idx]];
                idx = parent;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.data.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.compare(this.data[left], this.data[smallest]) < 0) smallest = left;
            if (right < len && this.compare(this.data[right], this.data[smallest]) < 0) smallest = right;
            if (smallest !== idx) {
                [this.data[idx], this.data[smallest]] = [this.data[smallest], this.data[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function dijkstra(V: number, edges: number[][], src: number): number[] {
    // adj[u] = {v, w} for every edge, stored in both directions.
    const adj: [number, number][][] = Array.from({ length: V }, () => []);
    for (const e of edges) {
        adj[e[0]].push([e[1], e[2]]);
        adj[e[1]].push([e[0], e[2]]);
    }

    const INT_MAX = 2147483647;
    const dist: number[] = new Array(V).fill(INT_MAX);   // INT_MAX = not reached yet
    // Min-heap of {distance, node}: the closest tentative node comes out first.
    const pq = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
    dist[src] = 0;
    pq.push([0, src]);

    while (!pq.isEmpty()) {
        const [d, u] = pq.pop()!;
        if (d > dist[u]) continue;   // stale entry: u was reached with a smaller distance

        for (const [v, w] of adj[u]) {
            if (d + w < dist[v]) {   // a shorter way to v through u
                dist[v] = d + w;
                pq.push([dist[v], v]);
            }
        }
    }
    return dist;
}

Complexity

Time O((V + E) log V)Space O(V + E)

Each undirected edge is looked at twice, once from each end, and each look pushes at most one heap entry. A heap operation costs O(log size), and the size is at most about 2E + 1. Stale pops cost time but never change the answer.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Relax every edge in both directions, V − 1 times	O(V · E)	O(V)
Better	Settle the closest unsettled node by scanning all V nodes	O(V² + E)	O(V + E)
Optimal	Pop the closest tentative node from a min-heap; skip stale entries	O((V + E) log V)	O(V + E)

Why does this belong to this pattern?

Clues in the problem statement

“shortest distance from src to every node”One source and a distance for every node: Dijkstra, returning the whole array.
“weighted edges”Plain BFS counts edges, not cost. Use a priority queue ordered by cost.
“w ≥ 0”Non-negative weights are what make the closest unfinished node final.

one source+non-negative weights+min-heap of (distance, node)+stale entries skipped→Shortest Paths (Dijkstra): min-heap with lazy deletion

This is the template for the whole sub-pattern. The next three questions change one thing each: Network Delay Time takes the largest distance, Maximum Probability multiplies and pops the largest first, Minimum Effort uses max instead of +. The rule that never changes is: pop the closest node, and skip any entry that is stale.

Don't make this mistake

Pattern confusion: BFS gives the fewest edges, not the least cost

✗ queue<int> q; ... if (dist[v] == INT_MAX) { dist[v] = dist[u] + w; q.push(v); }

✓ priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; ... if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }

On the dry run, BFS reaches node 1 straight from node 0 and fixes dist[1] = 4. But 0 → 2 → 1 costs 1 + 2 = 3. BFS also gives node 3 the value 6 (the true value is 4) and node 4 the value 9 (the true value is 7). BFS trusts the first arrival, and the first arrival is the route with the fewest edges, not the lowest cost.

Marking a node done when it is pushed, not when it is popped

✗ if (!done[v] && d + w < dist[v]) { dist[v] = d + w; done[v] = true; pq.push({dist[v], v}); }

✓ Mark a node done only when its live entry is popped, and relax from that node.

On the dry run, node 1 would be marked done at 4 as soon as node 0 pushes it. The route 0 → 2 → 1 (cost 3) is then never tried, because node 1 is already done, so node 1 stays at 4. A pushed distance can still drop.

Starting every distance at 0 instead of INT_MAX

✗ vector<int> dist(V, 0);

✓ vector<int> dist(V, INT_MAX); dist[src] = 0;

With every entry at 0, no edge ever looks shorter (d + w < 0 is never true), so nothing is relaxed. The whole output is 0 0 0 0 0 0, including node 5, which should be INT_MAX.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Shortest Paths (Weighted) translate into production architectures and low-level memory mechanics.

LLD Architecture