Dijkstra’s Algorithm

Ah yes, Dijkstra’s algorithm. The one you swear you’ll never forget, and yet somehow in every contest you end up trying BFS on weighted edges (“because it worked last time, right?”). Spoiler alert: BFS is not magic. If edges have weights other than 1, you’ll get the wrong answer faster than your WA verdict appears. So buckle up, because we’re about to roast your brute force instincts while learning to drive this algorithm properly.

1. Prerequisites (aka: What you should have Googled already)

• Graphs: You know… nodes, edges, adjacency lists. If not, go back to kindergarten.

• Weighted Edges: Numbers on edges that make life harder.

• Priority Queue / Heap: The data structure that makes Dijkstra run fast, not in geologic time.

• Greedy Algorithms: If you’ve ever picked the last slice of pizza without thinking of tomorrow, you’re qualified. 😂

2. Intuition (Why Dijkstra works, without making you cry)

Imagine you’re at node 0 (the “source”), and you want the cheapest Uber ride to every other node. Naturally, you’d start with your source (distance = 0), and always extend from the cheapest ride so far. That’s the greedy choice: if we’ve found the cheapest way to reach a node, no future path will magically beat it (because edge weights are non-negative — if they were negative, your Uber driver is paying you to ride, and that’s Bellman-Ford’s territory).

Mini Example:

Graph (5 nodes):

0 --(2)--> 1
0 --(4)--> 2
1 --(1)--> 2
1 --(7)--> 3
2 --(3)--> 3
3 --(1)--> 4

Adjacency list style:

0: [(1,2), (2,4)]
1: [(2,1), (3,7)]
2: [(3,3)]
3: [(4,1)]

Shortest distances from 0:

• 0 → 0 = 0

• 0 → 1 = 2

• 0 → 2 = 3 (via 0→1→2, not direct edge 0→2=4)

• 0 → 3 = 6 (via 0→1→2→3)

• 0 → 4 = 7 (add edge 3→4)

3. Formal Algorithm & Pseudocode

function Dijkstra(graph, source):
    dist[] = array of size |V|, filled with ∞
    dist[source] = 0
    pq = min-priority-queue
    pq.push((0, source))

    while pq is not empty:
        (d, u) = pq.pop()    // node with smallest dist
        if d > dist[u]: continue  // outdated entry
        for (v, w) in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pq.push((dist[v], v))

    return dist

4. Complexity & Quick Correctness Sketch

• Time: O((V+E) log V) (because every edge can cause at most one pq.push, each log V).

• Space: O(V + E) for storing graph and distance array.

• Why it’s correct: Once a node is popped from the queue with the smallest distance, we’ve proven it’s final (greedy + non-negative weights). No later update can reduce it.

5. Implementations

C# (with PriorityQueue in .NET 6+)

using System;
using System.Collections.Generic;

class DijkstraDemo
{
    public static int[] Dijkstra(List<(int v, int w)>[] graph, int source)
    {
        int n = graph.Length;
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[source] = 0;

        var pq = new PriorityQueue<int, int>();
        pq.Enqueue(source, 0);

        while (pq.Count > 0)
        {
            pq.TryDequeue(out int u, out int d);
            if (d > dist[u]) continue;

            foreach (var (v, w) in graph[u])
            {
                if (dist[u] + w < dist[v])
                {
                    dist[v] = dist[u] + w;
                    pq.Enqueue(v, dist[v]);
                }
            }
        }
        return dist;
    }

    static void Main()
    {
        var graph = new List<(int, int)>[5];
        for (int i = 0; i < 5; i++) graph[i] = new List<(int, int)>();

        graph[0].Add((1, 2));
        graph[0].Add((2, 4));
        graph[1].Add((2, 1));
        graph[1].Add((3, 7));
        graph[2].Add((3, 3));
        graph[3].Add((4, 1));

        int[] dist = Dijkstra(graph, 0);
        Console.WriteLine(string.Join(", ", dist));
        // Expected output: 0, 2, 3, 6, 7
    }
}

Python (with heapq)

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    pq = [(0, source)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

if __name__ == "__main__":
    graph = [
        [(1,2), (2,4)],   # node 0
        [(2,1), (3,7)],   # node 1
        [(3,3)],          # node 2
        [(4,1)],          # node 3
        []                # node 4
    ]
    print(dijkstra(graph, 0))
    # Expected: [0, 2, 3, 6, 7]

6. Worked Example Walkthrough

Queue evolution for the mini graph:

Start: dist = [0, ∞, ∞, ∞, ∞], pq = [(0,0)]
Pop (0,0): relax 1→2, 2→4
dist = [0,2,4,∞,∞], pq = [(2,1),(4,2)]
Pop (2,1): relax 2→1, 3→7
dist = [0,2,3,9,∞], pq = [(3,2),(4,2),(9,3)]
Pop (3,2): relax 3→3
dist = [0,2,3,6,∞], pq = [(4,2),(6,3),(9,3)]
Pop (6,3): relax 4→1
dist = [0,2,3,6,7], pq = [(7,4),(9,3)]
Done.

7. Some exercise

• 743. Network Delay Time (classic Dijkstra).

• 1631. Path With Minimum Effort.

• 1514. Path with Maximum Probability (slight tweak).

8. Full Problem Solution: 743. Network Delay Time

Problem:

Given a list of travel times (u,v,w), find the time it takes for all nodes to receive a signal from k. If impossible, return -1.

Why Dijkstra?

Non-negative weights, shortest path from single source to all nodes. Textbook Dijkstra.

Solution Steps:

1. Build adjacency list.

2. Run Dijkstra from k.

3. Answer = max of all distances, unless some node is unreachable.

Python Code

import heapq

def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n+1)]
    for u,v,w in times:
        graph[u].append((v,w))

    dist = [float('inf')] * (n+1)
    dist[k] = 0
    pq = [(0,k)]

    while pq:
        d,u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v,w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    ans = max(dist[1:])
    return -1 if ans == float('inf') else ans

# Test
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  
# Expected: 2

9. Hints to Spot Dijkstra ✅

• Single-source shortest path?

• Non-negative edge weights?

• Graph size up to ~10^5 edges?

• You like O(E log V) complexity better than TLE?

If yes, hello Dijkstra.

10. Common Mistakes & Debugging Tips

• Forgetting to skip outdated queue entries → infinite loops or wrong answers.

• Using BFS on weighted graphs → welcome to WA town.

• Not initializing dist properly (everything should start as ∞).

• Forgetting disconnected nodes → check for ∞ in results.

• Updating distances but forgetting to push new pair into PQ.