Dijkstra's Algorithm and Topological Sort

Weights and dependencies

When edges have non-negative weights, Dijkstra's algorithm finds the shortest distance from a source to every vertex. It keeps a priority queue (a heapq min-heap) of tentative distances, repeatedly takes the closest unsettled vertex, and relaxes its edges (if going through it gives a shorter route to a neighbour, update that neighbour). With a binary heap, it runs in O((V + E) log V). Python implementations commonly push duplicate entries and skip stale ones when popped (lazy deletion). For graphs with negative weights, use Bellman–Ford; for all-pairs shortest paths on small graphs, Floyd–Warshall; and for grids or maps with a good distance estimate, A* adds a heuristic to explore fewer nodes. Topological sorting orders the vertices of a DAG so that every edge goes from earlier to later, which is exactly a valid order for build steps, course prerequisites, task scheduling and spreadsheet recalculation. Kahn's algorithm repeatedly takes vertices with no remaining incoming edges; if some vertices are never freed, the graph has a cycle. The standard library offers graphlib.TopologicalSorter (Python 3.9+).

Dijkstra with heapq and a topological sort

Shortest delivery routes and a valid course order.

import heapq
from graphlib import TopologicalSorter

def dijkstra(graph: dict[str, dict[str, int]], source: str) -> dict[str, int]:
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                              # stale entry: a shorter path was found already
        for neighbour, weight in graph.get(node, {}).items():
            candidate = d + weight
            if candidate < dist.get(neighbour, float("inf")):
                dist[neighbour] = candidate       # relax the edge
                heapq.heappush(heap, (candidate, neighbour))
    return dist

roads = {
    "Warehouse": {"A": 4, "B": 1},
    "B": {"A": 2, "C": 5},
    "A": {"C": 1},
    "C": {},
}
print(dijkstra(roads, "Warehouse"))   # {'Warehouse': 0, 'A': 3, 'B': 1, 'C': 4}

prereqs = {                           # course: set of prerequisites
    "algorithms": {"data-structures"},
    "data-structures": {"python-basics"},
    "web-apis": {"python-basics"},
    "capstone": {"algorithms", "web-apis"},
}
order = list(TopologicalSorter(prereqs).static_order())
print(order)   # python-basics first, capstone last; e.g. ['python-basics', 'data-structures', 'web-apis', 'algorithms', 'capstone']

# a cycle raises graphlib.CycleError:
# TopologicalSorter({"a": {"b"}, "b": {"a"}}).static_order()

Dijkstra needs non-negative weights

With a negative edge, a settled vertex could later be reached more cheaply, breaking Dijkstra's assumptions. Use Bellman–Ford for negative weights, and check for negative cycles.

त्वरित जाँच: What does a topological sort require of the graph?

• It must be a directed acyclic graph (DAG)
• It must be undirected
• It must be weighted
• It must be complete