Shortest Paths on a DAG

Shortest paths pick the algorithm from edge weights: non-negative → Dijkstra; negative edges → Bellman–Ford; all pairs small n → Floyd–Warshall.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Relax edges: dist[v] = min(dist[v], dist[u]+w). DAG? Process in topo order once. Track parent to rebuild paths.

Try this in Python

import heapq


def dijkstra(adj: list[list[tuple[int, int]]], start: int) -> list[int]:
    n = len(adj)
    dist = [10**18] * n
    dist[start] = 0
    pq: list[tuple[int, int]] = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist


print(dijkstra([[(1, 4), (2, 1)], [(3, 1)], [(3, 2)]], 0))

Common mistakes

• Dijkstra with negative edges (wrong).
• Not handling disconnected nodes (INF).

Key takeaways

• State Dijkstra: node is (vertex, mode) when constraints exist.
• k-edge limit → BFS on expanded layer graph.