DSA sheet · Graphs · Dijkstra pattern

Dijkstra's Algorithm

This is the first problem of the Dijkstra pattern. The teacher builds the whole algorithm from scratch: start from BFS, throw away the visited array, and swap the normal queue for a min-heap that always gives the closest node first. Every later problem in this pattern (Network Delay Time, Cheapest Flights, Minimum Effort) is this same code with small changes, so this page is the base for all of them. The only thing you need beforehand is the heap data structure (she has a short video on it; Part 0 below covers what we need).

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graphs, weights and heaps: what you must know first
• Part A · Dijkstra: shortest distance from a source to every node
• Part B · Why plain BFS gives wrong answers when edges have weights
• Part C · Revision page

Part 0 · Before starting

Nodes, edges, directed and undirected

A graph is a set of nodes (also called vertices, the circles) joined by edges (the lines). Nodes are usually numbered 0 to V-1, where V is the number of nodes. E is the number of edges.

• Undirected edge (0)—(1): you can walk both ways, 0 to 1 and 1 to 0.
• Directed edge (0)→(1): one way only, like a one-way street.

Weighted edges

In a weighted graph every edge carries a number, its weight: the cost, the time or the length of that road. The edge [u, v, w] means "a road between u and v that costs w". In an undirected graph the same w is used in both directions: if 0 to 1 costs 4, then 1 to 0 also costs 4.

      4
 (0)—————(1)       the road between 0 and 1 costs 4,
                   in both directions (undirected)

The length of a path is the sum of its edge weights, not the number of edges. So a path with 3 cheap edges can be shorter than a path with 1 expensive edge. This one fact is why we need a new algorithm.

Reading the input and building an adjacency list

The question gives the graph as an edge list: a list of [u, v, w] triples. Looking through the whole list every time we want "the neighbours of node 3" would be slow. So first we build an adjacency list: for every node, a small list of (neighbour, weight) pairs. (The other storage, an adjacency matrix, is a V×V table where cell [u][v] holds the weight. It takes V² space, far too much for big V, so we don't use it here.)

V = 3
edges = [[0, 1, 1], [1, 2, 3], [0, 2, 6]]

graph = [[] for _ in range(V)]       # one empty list per node
for u, v, w in edges:
    graph[u].append((v, w))          # u can go to v, cost w
    graph[v].append((u, w))          # undirected: v can also go to u, cost w

print(graph)   # [[(1, 1), (2, 6)], [(0, 1), (2, 3)], [(1, 3), (0, 6)]]

BFS, the visited array, and shortest paths when every edge costs 1

BFS (Breadth First Search) uses a queue (collections.deque): put the start node in, then keep taking a node from the front and adding its unseen neighbours to the back. It spreads out layer by layer: first everything 1 edge away, then 2 edges away, and so on. A visited set stops us from adding the same node twice (otherwise a cycle would loop forever).

When every edge has weight 1, "fewest edges" and "shortest distance" are the same thing, so the BFS layer of a node is its shortest distance. That's why BFS solved the unweighted shortest-path problems earlier in this playlist (Shortest Path in Binary Matrix, Rotting Oranges, Word Ladder).

from collections import deque

def bfs_dist(graph, src):
    dist = [-1] * len(graph)        # -1 = not reached yet (also acts as visited)
    dist[src] = 0
    queue = deque([src])
    while queue:
        node = queue.popleft()
        for nei in graph[node]:
            if dist[nei] == -1:     # first time we see it = fewest edges
                dist[nei] = dist[node] + 1
                queue.append(nei)
    return dist

print(bfs_dist([[1, 2], [0, 2], [0, 1, 3], [2]], 0))   # [0, 1, 1, 2]

With weights, "fewest edges" is no longer "cheapest". Part B shows exactly how this breaks. Dijkstra fixes it.

The heap (priority queue) and Python's heapq

A min-heap is a container that always hands you its smallest item first, no matter in what order you put things in. Adding and removing both take O(log n) time. A heap used like this is also called a priority queue: a queue where the item with the best priority (here, the smallest number) jumps to the front.

In Python, heapq turns a normal list into a min-heap:

• heapq.heappush(pq, item): add an item.
• heapq.heappop(pq): remove and return the smallest item.
• If the items are tuples, Python compares the first element; only on a tie does it look at the second. So (distance, node) is ordered by distance, which is what we want.

import heapq

pq = []
heapq.heappush(pq, (8, 2))      # (distance, node)
heapq.heappush(pq, (4, 1))
heapq.heappush(pq, (10, 4))
print(heapq.heappop(pq))        # (4, 1)  smallest distance comes out first
print(heapq.heappop(pq))        # (8, 2)

Part A · Dijkstra's algorithm

GeeksforGeeks · Dijkstra Algorithm

1The question in simple words

You get an undirected, weighted graph with V nodes numbered 0 to V-1, and a list edges where each [u, v, w] is a road between u and v of length w (usable both ways). You also get a source node src.

Return a list dist where dist[i] = the shortest distance from src to node i. The distance from src to itself is 0.

The teacher's picture (she uses it for the whole video):

        4          6
  (0)——————(1)——————(4)
   |                  |
  8|                  |5
   |                  |
  (2)———————————————(3)
            10

She first reads it with source = 4:

So the answer for source 4 is [10, 6, 15, 5, 0] (index = node). There are always two ways round this ring, and we must pick the cheaper one for every node.

There is one source, so this is a single-source shortest path problem (not multi-source like Rotting Oranges). And just like with a tree's root or a linked list's head, a graph has no natural "start", so the question must tell us where to begin: that's src.

2What the constraints tell us

• The sizes are large (the teacher reads them as going up to about 10⁶). From her complexity video: more than about 10⁸ simple steps gives TLE (Time Limit Exceeded). So anything like O(V²) or O(V·E) is risky. We need something close to O(V + E), with at most a log factor.
• Edge weights are non-negative. Dijkstra depends on this (see the "why it's correct" note in step 4).
• The output is an integer list of size V, one slot per node. She always starts by asking "what do I return?", and here the answer shapes the whole solution: this list is our dist array.

3Intuition: a ripple that spreads in order of distance

Picture dropping a stone in water at the source. The ripple reaches near places first and far places later. Dijkstra copies that: always expand the node that is currently closest to the source, then use it to improve the guesses for its neighbours.

We keep two things:

• dist: our best-known distance to each node so far. It starts as "infinity" (unknown) and only ever goes down.
• a min-heap of (distance, node) "offers": "I can reach this node with this distance". The heap always gives us the smallest offer first.

It's BFS, except the queue is replaced by a min-heap, and there's no visited array.

4Building the logic from her examples

Question 1: where do we start? → the source, with distance 0

The source is given. Its distance to itself is 0, because we don't move at all. So dist[src] = 0 and the first heap entry is (0, src).

Question 2: BFS or DFS?

The question wants the distance to every node, so it is a traversal: we must visit all of them. Both DFS and BFS can traverse. The teacher picks BFS because this is a shortest-path question, and BFS (spreading outward) is the natural shape for shortest paths. With weights, BFS needs one upgrade (the heap), which we'll reach in Question 4.

Question 3: do we need a visited array? → No!

In every graph problem so far we kept a visited array so we'd never enter a node twice. Here that is wrong. Her example, with source 0:

  path A: 0 → 2 → 3          = 8 + 10     = 18
  path B: 0 → 1 → 4 → 3      = 4 + 6 + 5  = 15

Suppose we happen to reach node 3 through path A first, with 18, and mark it visited. Later path B arrives with 15, which is better. With a visited array we would refuse to enter 3 again and keep the wrong 18.

It's not just node 3. If 3 had a further neighbour, say node 6 with an edge of 1, then 6 should get 15+1 = 16, not 18+1 = 19. A better distance at one node has to flow onward to everything after it. So we must be allowed to visit a node again whenever we arrive with a smaller distance.

Question 4: which neighbour first? → the cheapest one (greedy) → min-heap

From 0 there are two neighbours: 1 (cost 4) and 2 (cost 8). Which should we handle first? We can't see the future: maybe the roads after 1 are expensive and the roads after 2 are cheap. But the greedy choice (take what looks best right now) is to continue from the node with the smallest distance so far, which is 1 with 4.

A normal queue gives nodes in the order they were added, not by distance. A min-heap ordered by distance gives the smallest one every time. That's the only real change from BFS.

Question 5: what do we start dist with? → infinity

Every update is "keep the smaller of the old value and the new one". For the very first real distance to win, the starting value must be bigger than anything: infinity (float('inf') in Python; the teacher's Java uses Integer.MAX_VALUE). Then min(inf, 4) = 4 and the 4 is saved. The source is the only exception: dist[src] = 0.

Question 6: what goes into the heap? → (distance, node)

• the node, so we know whose neighbours to look at and which dist slot to compare with;
• the distance we reached it with, so we can add the next edge weight to it;
• distance first, so the heap orders by it.

Question 7: what happens for each neighbour? → new distance, compare, push

When we pop (d, node) and look at an edge node → nei of weight w, the distance to nei through node is d + w: everything up to the parent, plus this one road.

• If d + w < dist[nei]: it's an improvement. Save it in dist[nei] and push (d + w, nei). This step is called relaxing the edge.
• Otherwise: we already know an equal or better way. Do nothing.

Her example: we pop node 1 with distance 4. Its neighbour 0 would get 4 + 4 = 8. But dist[0] = 0 already. Going 0→1→0 and then onward can never beat just starting from 0, so we stop there. Her words: going to 2 straight from 0 is cheaper than 1→0→2.

Question 8: the stale entry → skip it

A node can sit in the heap more than once. In her example node 3 is pushed first with 18 (from 2), then again with 15 (from 4). The heap gives (15, 3) first; we use it. Later (18, 3) comes out too, but dist[3] is already 15. This old entry is called stale (out of date).

Question 9: what do we return? → the dist list

When the heap is empty, every node's best distance is in dist. Her Java copies it into an ArrayList because GFG wants that type. In Python the list itself is the answer.

5Approach steps

1. Build the adjacency list from edges, adding each edge both ways.
2. Make dist of size V filled with infinity; set dist[src] = 0.
3. Make a min-heap with one entry (0, src).
4. While the heap is not empty: pop the smallest (d, node).
5. If d > dist[node], it's stale: continue.
6. For each (nei, w) of node: nd = d + w. If nd < dist[nei], set dist[nei] = nd and push (nd, nei).
7. Return dist.

6Code (Python)

import heapq

class Solution:
    def dijkstra(self, V, edges, src):
        graph = [[] for _ in range(V)]
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))         # undirected: both directions

        dist = [float('inf')] * V
        dist[src] = 0
        pq = [(0, src)]                     # (distance, node)

        while pq:
            d, node = heapq.heappop(pq)     # closest offer first
            if d > dist[node]:              # stale entry, a better one was used
                continue
            for nei, w in graph[node]:
                nd = d + w                  # distance to nei through node
                if nd < dist[nei]:          # only if it improves
                    dist[nei] = nd
                    heapq.heappush(pq, (nd, nei))
        return dist

7Code line by line

8Dry run: the heap and dist after every pop

Her picture, source = 0. Adjacency list (in the order the edges are read): 0: (1,4) (2,8) · 1: (0,4) (4,6) · 2: (0,8) (3,10) · 3: (2,10) (4,5) · 4: (1,6) (3,5). dist is written as [node0, node1, node2, node3, node4], ∞ = infinity.

Start: dist = [0, ∞, ∞, ∞, ∞], heap = [(0,0)].

Answer: [0, 4, 8, 15, 10]. Node 3 is reached by 0→1→4→3 (4+6+5 = 15), not by 0→2→3 (18).

  [0]——4——[4]——6——[10]
   |                 |
   8                 5
   |                 |
  [8]——————10——————[18]

  [0]——4——[4]——6——[10]
   |                 |
   8                 5
   |                 |
  [8]——————10——————[15]

  node : 0  1  2  3   4
  dist : 0  4  8  15  10

Each box shows the node's current dist value, drawn at the node's position in the picture (top row: 0, 1, 4; bottom row: 2, 3).

Notice the pop order: distances 0, 4, 8, 10, 15. They come out in increasing order. That's the ripple from step 3, and it's why each node's first real pop is final.

A second quick check (GFG example)

V = 3, edges [[0,1,1],[1,2,3],[0,2,6]], src = 2. Pop (0,2): node 1 gets 3, node 0 gets 6. Pop (3,1): node 0 gets 3+1 = 4 < 6, push (4,0). Pop (4,0): nothing improves. Pop (6,0): stale (6 > 4), skip. Answer [4, 3, 0]: going 2→1→0 (3+1) beats the direct road 2→0 (6).

9Complexity & remember

• Building the graph: O(V + E) time and space.
• The heap loop: the teacher counts the heap entries: every node can come in, and every edge can add another entry (that's where the duplicates like the two node-3 entries come from). So about V + E entries, each pushed and popped once at O(log) cost. Total O((V + E) log V). (Strictly the heap can hold up to E entries, so the log is log E. But E ≤ V², so log E ≤ 2 log V, which is the same thing in Big-O.)
• Space: O(V + E) for the graph and the heap, plus O(V) for dist (her Java also spends O(V) on the ArrayList it returns).

Her checklist for every Dijkstra question: ① build the adjacency list, ② decide how to travel (BFS), ③ set up the priority queue and decide min-heap or max-heap, ④ decide which value the heap is ordered by (here the distance, not the node), ⑤ know what to return.

Part B · Why plain BFS fails with weights

The teacher says "we go with BFS", but the BFS she builds has a heap and no visited array. It's worth seeing why the ordinary BFS from earlier videos can't be used as it is. (This part is extra explanation, written to answer the obvious doubt.)

1The question

Same question as Part A. We just try to answer it with the old tool: a normal queue plus a visited array, setting each node's distance the first time we see it.

2What the constraints tell us

Weights can be anything ≥ 0, and they can be very different from each other (1 next to 10). That's exactly what breaks BFS: BFS only counts edges.

3Intuition

BFS spreads by number of roads. Dijkstra spreads by total length. If one long road reaches a place in 1 step and three short roads reach it in 3 steps, BFS meets the place first through the long road and, because of visited, never looks again.

4The counterexample

           10
  (0)———————————(1)
    \           /
    1\         /1
      \       /
        (2)

From 0: the direct road to 1 costs 10, but 0→2→1 costs 1 + 1 = 2.

Plain BFS answers 10 for node 1. The true answer is 2. Wrong.

What if I keep BFS but drop visited and allow updates?

Then you get a correct answer (each improvement re-queues the node), but a node can be improved and re-queued many times, and every time all its successors get redone too. On bad graphs that grows far beyond V + E. The heap prevents this: because nodes come out in order of distance, a node's first real pop is already final, and the only repeats are the cheap stale entries we skip.

5Approach steps of the broken version

1. Queue with src, dist[src] = 0, src marked visited.
2. Pop a node; for every unvisited neighbour set dist = dist[node] + w, mark visited, push.
3. Return dist. The first distance found is never improved.

6Code (Python), kept here to show the bug

from collections import deque

def plain_bfs_dist(V, edges, src):
    graph = [[] for _ in range(V)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    dist = [float('inf')] * V
    dist[src] = 0
    visited = [False] * V
    visited[src] = True
    queue = deque([src])
    while queue:
        node = queue.popleft()
        for nei, w in graph[node]:
            if not visited[nei]:            # BUG: first arrival is locked in
                visited[nei] = True
                dist[nei] = dist[node] + w
                queue.append(nei)
    return dist

print(plain_bfs_dist(3, [[0, 1, 10], [0, 2, 1], [2, 1, 1]], 0))   # [0, 10, 1]  (wrong: node 1 should be 2)

7Code line by line: the two lines that differ from Dijkstra

8Dry run

Done in the table in step 4: node 1 is locked at 10 on the very first pop, and the cheaper route through 2 arrives too late. Run Dijkstra on the same graph: pop (0,0) → push (10,1), (1,2); pop (1,2) → 1 improves to 2, push (2,1); pop (2,1) → final; pop (10,1) → stale, skip. Answer [0, 2, 1] ✓.

9Complexity & remember

Plain BFS is O(V + E), faster than Dijkstra, but it's simply wrong on weighted graphs, so its speed doesn't matter.

Part C · Revision page

s = Solution()
print(s.dijkstra(5, [[0, 1, 4], [0, 2, 8], [1, 4, 6], [2, 3, 10], [4, 3, 5]], 0))   # [0, 4, 8, 15, 10]
print(s.dijkstra(5, [[0, 1, 4], [0, 2, 8], [1, 4, 6], [2, 3, 10], [4, 3, 5]], 4))   # [10, 6, 15, 5, 0]
print(s.dijkstra(3, [[0, 1, 1], [1, 2, 3], [0, 2, 6]], 2))                          # [4, 3, 0]
print(s.dijkstra(3, [[0, 1, 10], [0, 2, 1], [2, 1, 1]], 0))                         # [0, 2, 1]
print(s.dijkstra(1, [], 0))                                                         # [0]

Based on this video: Dijkstra's Algorithm