# Dijkstra's Algorithm and Topological Sort — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/g-paths

> Find weighted shortest paths and order dependencies.

## 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.

```python
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.

**Quiz:** What does a topological sort require of the graph?

- [x] It must be a directed acyclic graph (DAG)
- [ ] It must be undirected
- [ ] It must be weighted
- [ ] It must be complete

*Answer:* It must be a directed acyclic graph (DAG). A cycle means no order can put every vertex after all its prerequisites.