Dijkstra

Dijkstra’s Algorithm

Use when: Weighted graph, find shortest (minimum cost) path from a source node.

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

import heapq
 
def dijkstra(graph, src, n):
    # graph[u] = [(weight, v), ...]
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]  # (cost, node)
 
    while heap:
        cost, u = heapq.heappop(heap)
        if cost > dist[u]:  # stale entry, skip
            continue
        for w, v in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
 
    return dist  # dist[i] = min cost from src to node i

Common Variations

Single target (stop early):

if u == target:
    return dist[target]

With edge filtering (e.g. only edges >= T):

for w, v in graph[u]:
    if w >= T and dist[u] + w < dist[v]:
        ...

Track path:

prev = [-1] * n
# inside relaxation:
prev[v] = u

Signals in a Problem

• “Minimum cost/weight path”
• “Cheapest route”
• “Binary search on answer + feasibility check” (binary search on T, Dijkstra checks if path exists under constraint)