23. Dijkstra's Shortest Path Algorithm

What problem does this solve? Find the shortest path from a source vertex to ALL other vertices in a weighted graph with non-negative edges. This is GPS route-finding, network routing, and friend-suggestion distances.

1. How Dijkstra Works

Mental Model

Algorithm

1. Mark all vertices unvisited, set distance[source] = 0, others = ∞
2. Find unvisited vertex with minimum distance → visit it (mark visited)
3. For each neighbor, update distance if path through current vertex is shorter
4. Repeat until all reachable vertices visited

2. Implementation (Adjacency Matrix)

python
Run Inline
# runnable
import numpy as np
def dijkstra_matrix(WMat, s):
    """Dijkstra's algorithm using adjacency matrix.
    Time: O(V²) — find-min is O(V) per vertex
    """
    rows, cols, _ = WMat.shape
    INF = np.max(WMat) * rows + 1
    visited = {}
    distance = {}
    for v in range(rows):
        visited[v] = False
        distance[v] = INF
    distance[s] = 0
    for _ in range(rows):
        # Find unvisited vertex with minimum distance
        nextd = min(distance[v] for v in range(rows) if not visited[v])
        nextv = min([v for v in range(rows) if not visited[v] and distance[v] == nextd])
        if nextv is None or distance[nextv] == INF:
            break
        visited[nextv] = True
        # Update neighbors
        for v in range(cols):
            if WMat[nextv, v, 0] == 1 and not visited[v]:
                distance[v] = min(distance[v], distance[nextv] + WMat[nextv, v, 1])
    return distance
# Test
WM = np.zeros(shape=(4, 4, 2))
edges = [(0, 1, 10), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 1, 4), (2, 3, 8)]
for (i, j, w) in edges:
    WM[i, j, 0] = 1
    WM[i, j, 1] = w
print(f"Dijkstra matrix: {dijkstra_matrix(WM, 0)}")
# {0: 0, 1: 7, 2: 3, 3: 9}  (A→C→B→D = 3+4+2=9)

3. Implementation (Adjacency List)

python
Run Inline
# runnable
def dijkstra_list(WList, s):
    """Dijkstra's algorithm using adjacency list. O(V²)."""
    INF = 1 + sum(d for u in WList for (v, d) in WList[u])
    visited = {v: False for v in WList}
    distance = {v: INF for v in WList}
    distance[s] = 0
    for _ in WList:
        # Find unvisited vertex with minimum distance
        unvisited = [v for v in WList if not visited[v]]
        if not unvisited:
            break
        nextv = min(unvisited, key=lambda v: distance[v])
        if distance[nextv] == INF:
            break
        visited[nextv] = True
        for v, d in WList[nextv]:
            if not visited[v]:
                distance[v] = min(distance[v], distance[nextv] + d)
    return distance
# Test
WL = {
    0: [(1, 10), (2, 3)],
    1: [(2, 1), (3, 2)],
    2: [(1, 4), (3, 8)],
    3: []
}
print(f"Dijkstra list: {dijkstra_list(WL, 0)}")

4. Optimized with Heap (O((V+E) log V))

python
Run Inline
# runnable
import heapq
def dijkstra_heap(WList, s):
    """Dijkstra using binary heap for O((V+E) log V) performance."""
    INF = float('inf')
    distance = {v: INF for v in WList}
    distance[s] = 0
    # Min-heap of (distance, vertex)
    pq = [(0, s)]
    visited = set()
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in WList[u]:
            if d + w < distance[v]:
                distance[v] = d + w
                heapq.heappush(pq, (distance[v], v))
    return distance
print(f"Dijkstra heap: {dijkstra_heap(WL, 0)}")

5. Correctness & Limitations

Practice Questions

Answers

A1.

pseudo
Initial: A=0, B=∞, C=∞, D=∞
Visit A: A=0, B=4, C=2, D=∞
Visit C: A=0, B=min(4, 2+∞)=4, C=2, D=5
Visit B: A=0, B=4, C=2, D=min(5, 4+5)=5
Visit D: A=0, B=4, C=2, D=5

A2. Dijkstra "freezes" distances when a vertex is visited. A negative edge could later shorten a frozen distance, but visited vertices are never re-evaluated.

A3. O(V) for distances and visited arrays, plus O(E) for the adjacency list. With heap: O(V) for the heap.

A4. Maintain a parent dictionary. When updating distance[v], set parent[v] = nextv. At the end, trace back from target to source using parent pointers. Join Discord Previous22. Topological Sort & DAG Longest PathNext24. Bellman-Ford & Floyd-Warshall