Shortest Paths: Dijkstra, Bellman-Ford, A* and More

You ask a map app for the quickest way home. It does not try every road in the city. It knows a few clever tricks, and each trick works only under certain rules: no road takes negative time, the map has no loops of one-way streets, you only need one start. This lesson teaches the tricks, the rules each one needs, and how to pick the right one in ten seconds.

Learning Objectives

After this lesson, you will be able to:

Say what a shortest path is in a weighted graph, and why fewest edges is a different question
Run Dijkstra's algorithm by hand with a heap, write it with lazy deletion, and rebuild the route from a prev table
Show with a three-vertex example why Dijkstra needs non-negative weights
Order a dependency graph with Kahn's algorithm and with DFS, and find shortest and longest paths in a DAG
Use Bellman-Ford for negative edges and to detect a negative cycle, and Floyd-Warshall for every pair at once
Solve grid problems with 0-1 BFS, multi-source BFS and A*, and choose between all of these with a decision table

Prerequisites

Before You Start

Review

#The Shortest Path Question

Recall the words from the Graphs lesson. A graph has vertices (also called nodes) joined by edges, and a weighted graph gives every edge a number, its weight: a distance, a price, or a time. The cost of a path is the sum of the weights along it. A shortest path is the path with the smallest cost, and the source is the vertex you start from.

Shortest does not mean fewest edges. A road with six short hops can beat a road with one long hop. All the examples in this lesson use one graph, written as a list of its edges. Each edge works both ways.

text

A-B 4    A-C 1    B-C 2    B-D 5
C-D 8    C-E 10   D-E 2

The question comes in a few shapes: one source to every vertex, one source to one target, or every vertex to every other. The edges may all be equal, some may be zero, or some may be negative. Each shape has its own best tool. That is why this lesson has a table at the end.

#Recap: BFS Counts Edges, Not Weights

Breadth-first search (BFS) visits the source, then every vertex one edge away, then two edges away, and so on. It uses a queue, a line where the first one in is the first one out. The first time BFS reaches a vertex, no route with fewer edges exists. So when every edge counts the same, BFS is already a shortest-path algorithm.

pythonrunnable cell

from collections import deque

edges = [("A", "B", 4), ("A", "C", 1), ("C", "B", 2), ("B", "D", 5),
         ("C", "D", 8), ("C", "E", 10), ("D", "E", 2)]

graph = {}                                  # vertex -> list of (neighbor, weight)
for u, v, w in edges:
    graph.setdefault(u, []).append((v, w))
    graph.setdefault(v, []).append((u, w))  # undirected: store the edge both ways


def bfs_hops(graph, source):
    """Fewest edges from source to every reachable vertex. O(V + E) time, O(V) space."""
    hops = {source: 0}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v, _ in graph[u]:
            if v not in hops:
                hops[v] = hops[u] + 1
                queue.append(v)
    return hops


print(bfs_hops(graph, "A"))
# Output:
# {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2}

BFS says E is 2 edges from A, by the route A, C, E. That route costs 1 + 10 = 11. The cheapest route to E costs 10, and it uses four edges. BFS cannot see weights, so we need a new idea. The cost of BFS itself is O(V + E) time and O(V) space, because each vertex enters the queue once and each edge is looked at a constant number of times.

#Dijkstra: Always Settle the Closest Vertex

Dijkstra's algorithm is BFS with a heap in place of the queue. It keeps a table of tentative distances, the best totals found so far, which may still improve. It also keeps a heap of (distance, vertex) pairs. Each round it pops the smallest pair. That vertex becomes settled, which means its distance is final.

Why is it final? Any other route to that vertex must leave the settled vertices through an unsettled one. Every unsettled vertex is at least as far as the smallest pair, and weights are not negative, so adding more edges cannot make the total smaller. Then the algorithm relaxes each edge out of the new vertex: if going through it gives a shorter total to a neighbor, update the table and push a new pair.

Here is the whole run by hand, from A. The heap shows its pairs, smallest first.

Step	Pop	Table after (A, B, C, D, E)	Heap after
start	none	0, inf, inf, inf, inf	(0, A)
1	(0, A)	0, 4, 1, inf, inf	(1, C), (4, B)
2	(1, C)	0, 3, 1, 9, 11	(3, B), (4, B), (9, D), (11, E)
3	(3, B)	0, 3, 1, 8, 11	(4, B), (8, D), (9, D), (11, E)
4	(4, B) is stale, skip	unchanged	(8, D), (9, D), (11, E)
5	(8, D)	0, 3, 1, 8, 10	(9, D), (10, E), (11, E)
6	(9, D) is stale, skip	unchanged	(10, E), (11, E)
7	(10, E)	unchanged	(11, E)
8	(11, E) is stale, skip	unchanged	empty

In step 2, B dropped from 4 to 3 because the route A, C, B costs 1 + 2. The old pair (4, B) stayed in the heap. Python's heapq cannot lower or delete a pair in the middle without scanning the list, so we leave old pairs in place and skip them when they surface. A pair is stale when its distance is bigger than the table says. Skipping stale pairs is called lazy deletion.

The viewer below runs Dijkstra on this same graph. It picks the smallest distance by scanning a list, while our code asks a heap, but the choices are identical.

Dijkstra's Algorithm: Watch Each Vertex Get SettledInteractive

Step through the run and watch the distance table. Each vertex is settled in order of distance, and a settled distance never changes again.

Loading visualization...

Now the code. The prev table remembers which vertex each best distance came from, so the route can be rebuilt by walking backward from the target.

pythonrunnable cell

import heapq


def dijkstra(graph, source):
    """Cheapest cost from source to every reachable vertex. Weights must not be negative.

    Time O((V + E) log V). Extra space O(V + E): the heap can hold one pair per edge.
    """
    dist = {source: 0}
    prev = {source: None}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                      # stale pair: a better one was pushed later
            continue
        for v, w in graph[u]:
            new_d = d + w
            if v not in dist or new_d < dist[v]:
                dist[v] = new_d              # relax the edge
                prev[v] = u
                heapq.heappush(heap, (new_d, v))
    return dist, prev


def build_path(prev, target):
    """Walk back through prev, then reverse. Returns None when target is unreachable."""
    if target not in prev:
        return None
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]


dist, prev = dijkstra(graph, "A")
print(dist)
print(build_path(prev, "E"), dist["E"])
print(build_path(prev, "Z"))
# Output:
# {'A': 0, 'B': 3, 'C': 1, 'D': 8, 'E': 10}
# ['A', 'C', 'B', 'D', 'E'] 10
# None

The cost has a clear reason. Each successful relaxation pushes one pair, so there are at most E + 1 pairs, and each push or pop costs O(log V). A vertex scans its edges only when its one non-stale pair is popped, so edge scanning adds up to E. The total is O((V + E) log V) time. The distance table holds V entries and the heap up to E, so the extra space is O(V + E).

#Why Dijkstra Needs Non-Negative Weights

The proof above used one fact: adding an edge never makes a route cheaper. A negative weight breaks that fact. Here is the smallest graph that shows it, with arrows now one-way. S goes to A for 2, S goes to B for 3, and B goes to A for -2. The cheapest route to A is S, B, A, which costs 1.

What Do You Think?

A directed graph has the edges S to A (weight 2), S to B (weight 3) and B to A (weight -2). A textbook Dijkstra settles a vertex the moment it is popped, and never changes it afterward. What distance does it report for A?

pythonrunnable cell

negative = {"S": [("A", 2), ("B", 3)], "A": [], "B": [("A", -2)]}


def dijkstra_settled(graph, source):
    """The textbook version: a vertex is final the moment it is popped."""
    dist = {source: 0}
    done = set()
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue
        done.add(u)
        for v, w in graph[u]:
            if v not in done and (v not in dist or d + w < dist[v]):
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return dist


print(dijkstra_settled(negative, "S"))
print("route S, B, A costs", 3 + (-2))
print(dijkstra(negative, "S")[0])
# Output:
# {'S': 0, 'A': 2, 'B': 3}
# route S, B, A costs 1
# {'S': 0, 'A': 1, 'B': 3}

The lazy-deletion code from the last section happens to heal itself here. It relaxes by comparing distances, so when the cheaper pair (1, A) arrives, A is scanned again. Do not lean on this. With negative edges that version can scan the same vertex many times, and its proof is gone.

Worse is a negative cycle: a loop of edges whose weights add up to less than zero. Then no cheapest path exists. You can go around the loop again and again, getting cheaper each time, and the code never stops.

Note that an undirected graph with one negative edge already has a negative cycle: go along the edge and back. For graphs with negative edges, use Bellman-Ford, later in this lesson.

#Topological Sort: Kahn and DFS

Some graphs say "this must come before that". In a build, the config must be read before compiling, and compiling must happen before testing and packaging. Draw each rule as a one-way arrow. A topological sort puts all the vertices in one line so that every arrow points forward.

It exists only when the graph is a DAG, a directed acyclic graph: one-way arrows and no cycle. If A must precede B and B must precede A, no line works.

text

config -> compile, docs        compile -> test, package
docs -> package                test -> package

Kahn's algorithm uses the in-degree, the number of arrows pointing into a vertex. A vertex with in-degree 0 waits for nothing, so it can go first. Put it in the line, erase its arrows (lower the in-degree of what it points to), and any vertex that reaches 0 joins the queue. Trace it: config (0) goes first, which frees compile and docs. Compile frees test, docs lowers package to 1, and test finally frees package.

The DFS method works the other way. Walk depth first, and add a vertex to a list only when everything it points to is finished. Reverse the list at the end. A vertex has three states: unvisited, in progress (on the current walk), and finished. Meeting an in-progress vertex means the walk went around a cycle.

pythonrunnable cell

def topo_kahn(graph):
    """Kahn's algorithm. Returns an order, or None if there is a cycle. O(V + E) time, O(V) space."""
    indegree = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1
    queue = deque(v for v in graph if indegree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None   # cycle vertices never reach 0


def topo_dfs(graph):
    """DFS method. Returns an order, or None if there is a cycle. O(V + E) time, O(V) space."""
    NEW, ACTIVE, DONE = 0, 1, 2
    state = {v: NEW for v in graph}
    finished = []

    def visit(u):
        state[u] = ACTIVE
        for v in graph[u]:
            if state[v] == ACTIVE:           # an arrow back into the current walk
                return False
            if state[v] == NEW and not visit(v):
                return False
        state[u] = DONE
        finished.append(u)                   # everything u points to is already in the list
        return True

    for u in graph:
        if state[u] == NEW and not visit(u):
            return None
    return finished[::-1]


tasks = {"config": ["compile", "docs"], "compile": ["test", "package"],
         "docs": ["package"], "test": ["package"], "package": []}
loop = {"a": ["b"], "b": ["c"], "c": ["a"], "d": []}

print(topo_kahn(tasks))
print(topo_dfs(tasks))
print(topo_kahn(loop), topo_dfs(loop))
# Output:
# ['config', 'compile', 'docs', 'test', 'package']
# ['config', 'docs', 'compile', 'test', 'package']
# None None

Both methods cost O(V + E) time and O(V) extra space: each vertex and each arrow is handled once. The two orders differ and both are correct, because a DAG usually has many valid orders. Kahn reports a cycle when the line comes out shorter than the vertex count. The DFS version recurses as deep as the longest chain, so on a chain of thousands of vertices prefer Kahn.

Quick check

Kahn's algorithm gives ['config', 'compile', 'docs', 'test', 'package'] and the DFS method gives ['config', 'docs', 'compile', 'test', 'package']. What does that tell you?

#Shortest and Longest Paths in a DAG

A DAG gives a free speedup. Process the vertices in topological order. When you reach a vertex, every route into it has already been relaxed, so its distance is final. Relax its outgoing edges once and move on. There is no heap and no stale pair.

This costs O(V + E) time and O(V) extra space, and it works with negative weights, because a DAG has no cycle to run around. For the longest path, flip every weight's sign, find the shortest path, and flip the answer back. Longest paths are useful: in a project plan, the longest chain of tasks sets the minimum time to finish. It is called the critical path.

pythonrunnable cell

INF = float("inf")

dag = {"S": [("A", 3), ("B", 2)], "A": [("C", 4), ("D", 6)],
       "B": [("D", 1), ("C", 5)], "C": [("T", 2)], "D": [("T", 1)], "T": []}


def dag_shortest(dag, source):
    """Shortest cost from source in a DAG, negative weights allowed. O(V + E)."""
    order = topo_kahn({u: [v for v, _ in edges] for u, edges in dag.items()})
    dist = {u: INF for u in dag}
    dist[source] = 0
    for u in order:
        if dist[u] == INF:
            continue                          # not reachable from the source
        for v, w in dag[u]:
            dist[v] = min(dist[v], dist[u] + w)
    return dist


negated = {u: [(v, -w) for v, w in edges] for u, edges in dag.items()}
shortest = dag_shortest(dag, "S")
longest = {u: -d for u, d in dag_shortest(negated, "S").items()}
print("shortest to T:", shortest["T"])
print("longest to T:", longest["T"])
print(dag_shortest({"S": [("A", 4), ("B", 5)], "B": [("A", -3)], "A": []}, "S"))
# Output:
# shortest to T: 4
# longest to T: 10
# {'S': 0, 'B': 5, 'A': 2}

The shortest route to T is S, B, D, T (2 + 1 + 1 = 4) and the longest is S, A, D, T (3 + 6 + 1 = 10). The last line has a negative edge and still comes out right: A is 2, through B.

#Bellman-Ford: Negative Edges and Negative Cycles

Bellman-Ford uses brute force with a clever stopping rule. Relax every edge, then do it again, and keep going. After round r, every distance is correct for routes of at most r edges. A route with no repeated vertex has at most V - 1 edges, so V - 1 rounds are enough when there is no negative cycle.

What Do You Think?

A graph has 5 vertices and no negative cycle. Bellman-Ford relaxes every edge in each round. What is the most rounds it can need before all distances are final?

That last sentence is also the cycle test. If one more round, round V, can still improve a distance, then some route keeps getting cheaper by going around a loop, and a negative cycle is reachable from the source.

pythonrunnable cell

def bellman_ford(vertices, edges, source):
    """Shortest costs with negative edges allowed. Returns None on a reachable negative cycle.

    Time O(V * E): up to V - 1 rounds over E edges. Extra space O(V).
    """
    dist = {v: INF for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, w in edges:                 # edges are directed: u to v
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:                       # nothing improved: finished early
            break
    for u, v, w in edges:                     # one more round: any improvement is a cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None
    return dist


vertices = ["S", "A", "B", "C"]
roads = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 2), ("B", "C", 4)]
print(bellman_ford(vertices, roads, "S"))
print(bellman_ford(vertices, roads + [("C", "B", -2)], "S"))
# Output:
# {'S': 0, 'A': 2, 'B': 5, 'C': 4}
# None

The route S, B, A takes 5 - 3 = 2, which beats the direct edge of 4. The second call adds C to B at -2. Now B, A, C, B is a loop costing -3 + 2 - 2 = -3, so the function returns None.

The cost is O(V·E) time, much slower than Dijkstra, and O(V) extra space. The edge order does not change the answer, but it changes how soon the early exit happens. The same five edges listed in reverse need three rounds that change something instead of one.

#Floyd-Warshall: All Pairs

Sometimes you need the distance from every vertex to every other: a table of travel times between cities. You could run Dijkstra from each vertex. Floyd-Warshall does it in one short triple loop.

It allows the vertices as middle stops one at a time. After handling the first k vertices, dist[i][j] holds the cheapest route from i to j that uses only those k vertices as stops. To add the next vertex k, a route from i to j either avoids k or goes i to k and then k to j.

pythonrunnable cell

def floyd_warshall(vertices, edges):
    """Cheapest cost between every pair. O(V³) time, O(V²) space."""
    dist = {u: {v: (0 if u == v else INF) for v in vertices} for u in vertices}
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
    for k in vertices:                        # k MUST be the outermost loop
        for i in vertices:
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


towns = ["A", "B", "C", "D"]
links = [("A", "B", 2), ("B", "C", 4), ("B", "D", 1), ("C", "D", 5), ("D", "C", 1)]
table = floyd_warshall(towns, links)
for u in towns:
    print(u, [table[u][v] for v in towns])
# Output:
# A [0, 2, 4, 3]
# B [inf, 0, 2, 1]
# C [inf, inf, 0, 5]
# D [inf, inf, 1, 0]

Read row A: reaching C costs 4, not 6, because A, B, D, C costs 2 + 1 + 1. An inf means no route exists: nothing leads back to A. Three nested loops over V vertices give O(V³) time, and the V by V table is O(V²) space. That is fine for a few hundred vertices. If a vertex ends with dist[i][i] < 0, it sits on a negative cycle.

When the graph is large and sparse, run Dijkstra from every vertex instead: V runs of O((V + E) log V) each beat V³ when E is small.

#0-1 BFS and Multi-Source BFS

Two cheap variants of BFS cover many grid problems. A grid is a graph: each cell is a vertex, and each cell touches its four neighbors, so E is at most 4V.

In 0-1 BFS every edge costs 0 or 1. Use a deque. When a move costs 0, push the cell on the front. When it costs 1, push it on the back. The deque always holds cells in order of distance, with at most two different distances, which is what a heap would have given us.

Time is O(V + E) and space is O(V). A cell can be added at most twice: once with a distance one too high, and once more with the better distance.

In multi-source BFS there are several starting points. Put all of them in the queue at distance 0 before the first step. One BFS then gives every cell its distance to the nearest source. The cost is O(V + E), not one BFS per source.

pythonrunnable cell

walls = ["..#..",
         "..#..",
         "###..",
         ".....",
         "....."]


def fewest_walls(grid):
    """0-1 BFS from the top left to the bottom right; stepping onto # costs 1 (break it)."""
    rows, cols = len(grid), len(grid[0])
    dist = [[INF] * cols for _ in range(rows)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols:
                cost = 1 if grid[nr][nc] == "#" else 0
                if dist[r][c] + cost < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + cost
                    if cost == 0:
                        dq.appendleft((nr, nc))   # free move: front of the line
                    else:
                        dq.append((nr, nc))       # costly move: back of the line
    return dist[rows - 1][cols - 1]


city = ["S..#.",
        "..#..",
        "#...S",
        "..#..",
        "S...."]


def nearest_station(grid):
    """Multi-source BFS: steps from every open cell to the nearest S. -1 marks a wall."""
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "S":
                dist[r][c] = 0
                queue.append((r, c))              # every source starts at distance 0
    while queue:
        r, c = queue.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist


print(fewest_walls(walls))
for row in nearest_station(city):
    print(" ".join("#" if x == -1 else str(x) for x in row))
# Output:
# 1
# 0 1 2 # 2
# 1 2 # 2 1
# # 3 2 1 0
# 1 2 # 2 1
# 0 1 2 3 2

The top-left room is sealed, so one wall must be broken, and the answer is 1. In the second grid every cell shows how far it is from its closest station.

#A* Search on a Grid

Dijkstra spreads out in all directions, even away from the goal. If you know roughly where the goal is, you can aim. A-star (written A*, said "A star") orders the heap by g + h, where g is the cost so far and h is a heuristic: a cheap guess of the cost still to go. Dijkstra is the special case h = 0.

A guess must follow one rule to keep the answer exact. It must be admissible, which means it never guesses more than the true remaining cost. On a grid where each step costs 1 and you move in four directions, the Manhattan distance (rows apart plus columns apart) is admissible, because you cannot get there in fewer steps than that, even with no walls.

What Do You Think?

On a 10 by 10 grid with a wall between start and goal, Dijkstra finds the shortest route and expands 76 cells. A* with the Manhattan distance runs on the same grid. Which result do you expect?

pythonrunnable cell

grid = ["..........",
        "..........",
        "....####..",
        "....#.....",
        "....#.....",
        "....#.....",
        "..........",
        "..........",
        "..........",
        ".........."]


def search(grid, start, goal, scale):
    """Dijkstra when scale is 0, A* with Manhattan distance when scale is 1.

    Returns (cost, cells expanded). Worst case O((V + E) log V) like Dijkstra, space O(V).
    """
    rows, cols = len(grid), len(grid[0])

    def guess(cell):
        return scale * (abs(cell[0] - goal[0]) + abs(cell[1] - goal[1]))

    best = {start: 0}
    heap = [(guess(start), 0, start)]            # (g + h, g, cell)
    expanded = 0
    while heap:
        _, g, cell = heapq.heappop(heap)
        if g > best[cell]:
            continue                              # stale pair
        expanded += 1
        if cell == goal:
            return g, expanded
        r, c = cell
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
                if g + 1 < best.get((nr, nc), INF):
                    best[(nr, nc)] = g + 1
                    heapq.heappush(heap, (g + 1 + guess((nr, nc)), g + 1, (nr, nc)))
    return None, expanded


open_cells = sum(row.count(".") for row in grid)
print("open cells:", open_cells)
print("Dijkstra:", search(grid, (3, 1), (3, 8), 0))
print("A*:      ", search(grid, (3, 1), (3, 8), 1))
# Output:
# open cells: 93
# Dijkstra: (11, 76)
# A*:       (11, 25)

Both find the cost 11. Dijkstra expands 76 of the 93 open cells, and A* only 25. A* has the same worst case as Dijkstra, O((V + E) log V) time and O(V) space, and a bad guess can cost it the whole saving. A good guess is the whole point.

#Which Algorithm? A Decision Table

Ask three questions in order: are all the weights equal, can any be negative, and do you need one source or every pair?

Situation	Use	Time	Why
Every edge costs the same	BFS	O(V + E)	fewest edges is the cheapest route
Edges cost 0 or 1	0-1 BFS	O(V + E)	a deque stands in for the heap
Many starting points, one question	Multi-source BFS	O(V + E)	start the queue with all sources
Weights not negative, one source	Dijkstra	O((V + E) log V)	the heap settles the closest vertex
Not negative, and a good guess to one goal	A*	at most Dijkstra's	the guess skips unhelpful areas
No cycles (a DAG), any weights	Topological order, relax once	O(V + E)	no heap, negatives are fine
Negative edges, one source	Bellman-Ford	O(V·E)	repeated rounds, and it spots negative cycles
Every pair, small graph	Floyd-Warshall	O(V³)	three short loops
Every pair, large sparse graph	Dijkstra from each vertex	V times O((V + E) log V)	cheaper than V³ when E is small

#Where This Shows Up

A route planner models roads as edges with travel times and runs Dijkstra or A* with a map-distance guess. Real services add heavy precomputation on top, but the core question is the one in this lesson.
Internet routers share link costs and compute shortest routes. OSPF, a protocol used inside networks, runs Dijkstra, and the older RIP protocol is built on the Bellman-Ford idea.
Build tools, package managers and CI pipelines use topological sort to decide what to run first, and they report a circular dependency when Kahn's line comes out short.
A project plan is a DAG of tasks. The longest path is the critical path, so a delay on it delays the whole project.
A negative cycle in a table of currency exchange rates (using the negative logarithm of each rate as the weight) is a profit loop. Bellman-Ford finds it.
In speech and language models, Viterbi decoding finds the best sequence of hidden states. It is a shortest path through a DAG of states, solved with the same relax-in-order idea.

#Common Mistakes

Watch Out

Floyd-Warshall with the loops in the wrong order

Fix: Make the middle stop k the outermost loop. Then each pass has finished using the earlier stops everywhere before the next stop is added.

pythonrunnable cell

def floyd_warshall_wrong(vertices, edges):
    dist = {u: {v: (0 if u == v else INF) for v in vertices} for u in vertices}
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
    for i in vertices:                        # k should be out here
        for j in vertices:
            for k in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


wrong = floyd_warshall_wrong(towns, links)
print(wrong["A"]["C"], table["A"]["C"])
# Output:
# 6 4

The code looks almost the same and gives 6 for A to C, where the right answer is 4. With k innermost, the route A, B, D, C needs D as a stop after B is already used. That information has not been built yet when the pair (A, C) is checked. The result is a wrong number with no error, which is the worst kind of bug.

Watch Out

An A* guess that is bigger than the truth

Fix: Use a guess that never overestimates, like the Manhattan distance on a four-direction grid. If you must overestimate, accept that the route may not be the shortest.

pythonrunnable cell

spiral = ["..........",
          ".########.",
          ".#......#.",
          ".#.####.#.",
          ".#.#..#.#.",
          ".#.#.##.#.",
          "...#......"]

print("scale 0:", search(spiral, (0, 0), (4, 4), 0))
print("scale 1:", search(spiral, (0, 0), (4, 4), 1))
print("scale 10:", search(spiral, (0, 0), (4, 4), 10))
# Output:
# scale 0: (22, 43)
# scale 1: (22, 43)
# scale 10: (26, 33)

Multiplying the guess by 10 makes it larger than the real remaining cost, and A* trusts it. It rushes toward the goal, expands fewer cells (33), and returns a route of cost 26 instead of 22. The scale 1 run is also a reminder that a good guess cannot help when the goal sits inside a spiral: the straight-line direction points into a wall, and A* expands 43 cells, exactly as many as Dijkstra.

#Try It: Five Problems

Work through the ladder in order. Problem 3 builds on the Kahn idea, problem 4 has a bug to find, and problem 5 asks for a limit on the number of edges. The results print in a fixed order, so you can compare them with the description in the tests line.

pythonplayground.py · Pyodide

import heapq
from collections import deque

INF = float("inf")

# 1. Fewest hops. Return the number of edges on the shortest route from start to goal (BFS), or -1.
def fewest_hops(graph, start, goal):
  # TODO: BFS with a hops dict; return hops[goal] when found
  return -1

# 2. Cheapest cost. Finish Dijkstra: return the cost from start to goal, or -1 if unreachable.
def cheapest(graph, start, goal):
  dist = {start: 0}
  heap = [(0, start)]
  while heap:
      d, u = heapq.heappop(heap)
      # TODO: skip the stale pair, then relax each edge (v, w) out of u and push improvements
      pass
  return dist.get(goal, -1)

# 3. Build order. Return the tasks in an order that respects the arrows, or None if there is a cycle.
def build_order(deps):
  # TODO: Kahn's algorithm with in-degrees and a deque
  return None

# 4. Find the bug. This should give the all-pairs table, but A to C comes out wrong. Fix it.
def all_pairs(vertices, edges):
  dist = {u: {v: (0 if u == v else INF) for v in vertices} for u in vertices}
  for u, v, w in edges:
      dist[u][v] = min(dist[u][v], w)
  for i in vertices:
      for j in vertices:
          for k in vertices:
              if dist[i][k] + dist[k][j] < dist[i][j]:
                  dist[i][j] = dist[i][k] + dist[k][j]
  return dist

# 5. At most k stops. Return the cheapest cost from src to dst using at most k + 1 edges, or -1.
#    Hint: run k + 1 rounds of Bellman-Ford, and in each round read distances from a copy of the last round.
def cheapest_with_stops(flights, src, dst, k):
  # TODO
  return -1

roads = {"A": [("B", 4), ("C", 1)], "B": [("D", 5)], "C": [("B", 2), ("D", 8)], "D": []}
print(fewest_hops(roads, "A", "D"), cheapest(roads, "A", "D"), cheapest(roads, "D", "A"))
print(build_order({"config": ["compile", "docs"], "compile": ["package"], "docs": ["package"], "package": []}))
print(build_order({"a": ["b"], "b": ["a"]}))
table = all_pairs(["A", "B", "C", "D"], [("A", "B", 2), ("B", "C", 4), ("B", "D", 1), ("C", "D", 5), ("D", "C", 1)])
print(table["A"]["C"])
flights = [("A", "B", 100), ("B", "C", 100), ("A", "C", 500), ("C", "D", 100)]
print([cheapest_with_stops(flights, "A", "D", k) for k in range(3)])

Tests · Expected output: line 1 is 2 8 -1 (fewest hops, cheapest cost, unreachable). Line 2 is ['config', 'compile', 'docs', 'package']. Line 3 is None. Line 4 is 4 (with the bug it prints 6). Line 5 is [-1, 600, 300].

#Recap

A shortest path is the route with the smallest total weight, which can differ from the route with the fewest edges. BFS handles equal weights in O(V + E). Dijkstra handles non-negative weights with a heap: pop the closest vertex, settle it, relax its edges, and skip stale pairs. The run costs O((V + E) log V).

A negative edge breaks the settle step, and a negative cycle means no cheapest path exists.

Topological sort orders a DAG in O(V + E), by Kahn's in-degree queue or by DFS, and it lets you find shortest or longest paths in a DAG without a heap.

Bellman-Ford relaxes every edge for V - 1 rounds in O(V·E) time and detects negative cycles. Floyd-Warshall fills an all-pairs table in O(V³) time with k as the outermost loop. 0-1 BFS and multi-source BFS are BFS with a deque or several starts. A* adds an admissible guess to Dijkstra to expand fewer cells.

Quick Check1 / 6

A graph has edges of weight 1, 2 and 5, and none are negative. You need the cheapest route from one source to every other vertex. Which algorithm fits best?

Recap

Key Takeaways

Shortest means smallest total weight, which is a different question from fewest edges
Dijkstra settles the closest vertex with a heap and skips stale pairs, in O((V + E) log V) time, and it needs non-negative weights
Topological sort exists only for a DAG, costs O(V + E), and a short Kahn result means a cycle
Bellman-Ford costs O(V·E), allows negative edges, and one extra round that still improves means a negative cycle
Floyd-Warshall fills every pair in O(V³) time and O(V²) space, and k must be the outermost loop
Use BFS for equal weights, 0-1 BFS for 0 or 1, and A* only with a guess that never overestimates

Shortest Paths: Dijkstra, Bellman-Ford, A* and More

Learning Objectives

After this lesson, you will be able to:

Say what a shortest path is in a weighted graph, and why fewest edges is a different question
Run Dijkstra's algorithm by hand with a heap, write it with lazy deletion, and rebuild the route from a prev table
Show with a three-vertex example why Dijkstra needs non-negative weights
Order a dependency graph with Kahn's algorithm and with DFS, and find shortest and longest paths in a DAG
Use Bellman-Ford for negative edges and to detect a negative cycle, and Floyd-Warshall for every pair at once
Solve grid problems with 0-1 BFS, multi-source BFS and A*, and choose between all of these with a decision table

Prerequisites

Before You Start

Review

#The Shortest Path Question

text

A-B 4    A-C 1    B-C 2    B-D 5
C-D 8    C-E 10   D-E 2

#Recap: BFS Counts Edges, Not Weights

pythonrunnable cell

from collections import deque

edges = [("A", "B", 4), ("A", "C", 1), ("C", "B", 2), ("B", "D", 5),
         ("C", "D", 8), ("C", "E", 10), ("D", "E", 2)]

graph = {}                                  # vertex -> list of (neighbor, weight)
for u, v, w in edges:
    graph.setdefault(u, []).append((v, w))
    graph.setdefault(v, []).append((u, w))  # undirected: store the edge both ways


def bfs_hops(graph, source):
    """Fewest edges from source to every reachable vertex. O(V + E) time, O(V) space."""
    hops = {source: 0}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v, _ in graph[u]:
            if v not in hops:
                hops[v] = hops[u] + 1
                queue.append(v)
    return hops


print(bfs_hops(graph, "A"))
# Output:
# {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2}

#Dijkstra: Always Settle the Closest Vertex

Here is the whole run by hand, from A. The heap shows its pairs, smallest first.

Step	Pop	Table after (A, B, C, D, E)	Heap after
start	none	0, inf, inf, inf, inf	(0, A)
1	(0, A)	0, 4, 1, inf, inf	(1, C), (4, B)
2	(1, C)	0, 3, 1, 9, 11	(3, B), (4, B), (9, D), (11, E)
3	(3, B)	0, 3, 1, 8, 11	(4, B), (8, D), (9, D), (11, E)
4	(4, B) is stale, skip	unchanged	(8, D), (9, D), (11, E)
5	(8, D)	0, 3, 1, 8, 10	(9, D), (10, E), (11, E)
6	(9, D) is stale, skip	unchanged	(10, E), (11, E)
7	(10, E)	unchanged	(11, E)
8	(11, E) is stale, skip	unchanged	empty

The viewer below runs Dijkstra on this same graph. It picks the smallest distance by scanning a list, while our code asks a heap, but the choices are identical.

Dijkstra's Algorithm: Watch Each Vertex Get SettledInteractive

Step through the run and watch the distance table. Each vertex is settled in order of distance, and a settled distance never changes again.

Loading visualization...

Now the code. The prev table remembers which vertex each best distance came from, so the route can be rebuilt by walking backward from the target.

pythonrunnable cell

import heapq


def dijkstra(graph, source):
    """Cheapest cost from source to every reachable vertex. Weights must not be negative.

    Time O((V + E) log V). Extra space O(V + E): the heap can hold one pair per edge.
    """
    dist = {source: 0}
    prev = {source: None}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                      # stale pair: a better one was pushed later
            continue
        for v, w in graph[u]:
            new_d = d + w
            if v not in dist or new_d < dist[v]:
                dist[v] = new_d              # relax the edge
                prev[v] = u
                heapq.heappush(heap, (new_d, v))
    return dist, prev


def build_path(prev, target):
    """Walk back through prev, then reverse. Returns None when target is unreachable."""
    if target not in prev:
        return None
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]


dist, prev = dijkstra(graph, "A")
print(dist)
print(build_path(prev, "E"), dist["E"])
print(build_path(prev, "Z"))
# Output:
# {'A': 0, 'B': 3, 'C': 1, 'D': 8, 'E': 10}
# ['A', 'C', 'B', 'D', 'E'] 10
# None

#Why Dijkstra Needs Non-Negative Weights

What Do You Think?

pythonrunnable cell

negative = {"S": [("A", 2), ("B", 3)], "A": [], "B": [("A", -2)]}


def dijkstra_settled(graph, source):
    """The textbook version: a vertex is final the moment it is popped."""
    dist = {source: 0}
    done = set()
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue
        done.add(u)
        for v, w in graph[u]:
            if v not in done and (v not in dist or d + w < dist[v]):
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return dist


print(dijkstra_settled(negative, "S"))
print("route S, B, A costs", 3 + (-2))
print(dijkstra(negative, "S")[0])
# Output:
# {'S': 0, 'A': 2, 'B': 3}
# route S, B, A costs 1
# {'S': 0, 'A': 1, 'B': 3}

Note that an undirected graph with one negative edge already has a negative cycle: go along the edge and back. For graphs with negative edges, use Bellman-Ford, later in this lesson.

#Topological Sort: Kahn and DFS

It exists only when the graph is a DAG, a directed acyclic graph: one-way arrows and no cycle. If A must precede B and B must precede A, no line works.

text

config -> compile, docs        compile -> test, package
docs -> package                test -> package

pythonrunnable cell

def topo_kahn(graph):
    """Kahn's algorithm. Returns an order, or None if there is a cycle. O(V + E) time, O(V) space."""
    indegree = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1
    queue = deque(v for v in graph if indegree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None   # cycle vertices never reach 0


def topo_dfs(graph):
    """DFS method. Returns an order, or None if there is a cycle. O(V + E) time, O(V) space."""
    NEW, ACTIVE, DONE = 0, 1, 2
    state = {v: NEW for v in graph}
    finished = []

    def visit(u):
        state[u] = ACTIVE
        for v in graph[u]:
            if state[v] == ACTIVE:           # an arrow back into the current walk
                return False
            if state[v] == NEW and not visit(v):
                return False
        state[u] = DONE
        finished.append(u)                   # everything u points to is already in the list
        return True

    for u in graph:
        if state[u] == NEW and not visit(u):
            return None
    return finished[::-1]


tasks = {"config": ["compile", "docs"], "compile": ["test", "package"],
         "docs": ["package"], "test": ["package"], "package": []}
loop = {"a": ["b"], "b": ["c"], "c": ["a"], "d": []}

print(topo_kahn(tasks))
print(topo_dfs(tasks))
print(topo_kahn(loop), topo_dfs(loop))
# Output:
# ['config', 'compile', 'docs', 'test', 'package']
# ['config', 'docs', 'compile', 'test', 'package']
# None None

Quick check

Kahn's algorithm gives ['config', 'compile', 'docs', 'test', 'package'] and the DFS method gives ['config', 'docs', 'compile', 'test', 'package']. What does that tell you?

#Shortest and Longest Paths in a DAG

pythonrunnable cell

INF = float("inf")

dag = {"S": [("A", 3), ("B", 2)], "A": [("C", 4), ("D", 6)],
       "B": [("D", 1), ("C", 5)], "C": [("T", 2)], "D": [("T", 1)], "T": []}


def dag_shortest(dag, source):
    """Shortest cost from source in a DAG, negative weights allowed. O(V + E)."""
    order = topo_kahn({u: [v for v, _ in edges] for u, edges in dag.items()})
    dist = {u: INF for u in dag}
    dist[source] = 0
    for u in order:
        if dist[u] == INF:
            continue                          # not reachable from the source
        for v, w in dag[u]:
            dist[v] = min(dist[v], dist[u] + w)
    return dist


negated = {u: [(v, -w) for v, w in edges] for u, edges in dag.items()}
shortest = dag_shortest(dag, "S")
longest = {u: -d for u, d in dag_shortest(negated, "S").items()}
print("shortest to T:", shortest["T"])
print("longest to T:", longest["T"])
print(dag_shortest({"S": [("A", 4), ("B", 5)], "B": [("A", -3)], "A": []}, "S"))
# Output:
# shortest to T: 4
# longest to T: 10
# {'S': 0, 'B': 5, 'A': 2}

The shortest route to T is S, B, D, T (2 + 1 + 1 = 4) and the longest is S, A, D, T (3 + 6 + 1 = 10). The last line has a negative edge and still comes out right: A is 2, through B.

#Bellman-Ford: Negative Edges and Negative Cycles

What Do You Think?

A graph has 5 vertices and no negative cycle. Bellman-Ford relaxes every edge in each round. What is the most rounds it can need before all distances are final?

pythonrunnable cell

def bellman_ford(vertices, edges, source):
    """Shortest costs with negative edges allowed. Returns None on a reachable negative cycle.

    Time O(V * E): up to V - 1 rounds over E edges. Extra space O(V).
    """
    dist = {v: INF for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, w in edges:                 # edges are directed: u to v
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:                       # nothing improved: finished early
            break
    for u, v, w in edges:                     # one more round: any improvement is a cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None
    return dist


vertices = ["S", "A", "B", "C"]
roads = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 2), ("B", "C", 4)]
print(bellman_ford(vertices, roads, "S"))
print(bellman_ford(vertices, roads + [("C", "B", -2)], "S"))
# Output:
# {'S': 0, 'A': 2, 'B': 5, 'C': 4}
# None

The route S, B, A takes 5 - 3 = 2, which beats the direct edge of 4. The second call adds C to B at -2. Now B, A, C, B is a loop costing -3 + 2 - 2 = -3, so the function returns None.

#Floyd-Warshall: All Pairs

Sometimes you need the distance from every vertex to every other: a table of travel times between cities. You could run Dijkstra from each vertex. Floyd-Warshall does it in one short triple loop.

pythonrunnable cell

def floyd_warshall(vertices, edges):
    """Cheapest cost between every pair. O(V³) time, O(V²) space."""
    dist = {u: {v: (0 if u == v else INF) for v in vertices} for u in vertices}
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
    for k in vertices:                        # k MUST be the outermost loop
        for i in vertices:
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


towns = ["A", "B", "C", "D"]
links = [("A", "B", 2), ("B", "C", 4), ("B", "D", 1), ("C", "D", 5), ("D", "C", 1)]
table = floyd_warshall(towns, links)
for u in towns:
    print(u, [table[u][v] for v in towns])
# Output:
# A [0, 2, 4, 3]
# B [inf, 0, 2, 1]
# C [inf, inf, 0, 5]
# D [inf, inf, 1, 0]

When the graph is large and sparse, run Dijkstra from every vertex instead: V runs of O((V + E) log V) each beat V³ when E is small.

#0-1 BFS and Multi-Source BFS

Two cheap variants of BFS cover many grid problems. A grid is a graph: each cell is a vertex, and each cell touches its four neighbors, so E is at most 4V.

Time is O(V + E) and space is O(V). A cell can be added at most twice: once with a distance one too high, and once more with the better distance.

pythonrunnable cell

walls = ["..#..",
         "..#..",
         "###..",
         ".....",
         "....."]


def fewest_walls(grid):
    """0-1 BFS from the top left to the bottom right; stepping onto # costs 1 (break it)."""
    rows, cols = len(grid), len(grid[0])
    dist = [[INF] * cols for _ in range(rows)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols:
                cost = 1 if grid[nr][nc] == "#" else 0
                if dist[r][c] + cost < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + cost
                    if cost == 0:
                        dq.appendleft((nr, nc))   # free move: front of the line
                    else:
                        dq.append((nr, nc))       # costly move: back of the line
    return dist[rows - 1][cols - 1]


city = ["S..#.",
        "..#..",
        "#...S",
        "..#..",
        "S...."]


def nearest_station(grid):
    """Multi-source BFS: steps from every open cell to the nearest S. -1 marks a wall."""
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "S":
                dist[r][c] = 0
                queue.append((r, c))              # every source starts at distance 0
    while queue:
        r, c = queue.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist


print(fewest_walls(walls))
for row in nearest_station(city):
    print(" ".join("#" if x == -1 else str(x) for x in row))
# Output:
# 1
# 0 1 2 # 2
# 1 2 # 2 1
# # 3 2 1 0
# 1 2 # 2 1
# 0 1 2 3 2

The top-left room is sealed, so one wall must be broken, and the answer is 1. In the second grid every cell shows how far it is from its closest station.

#A* Search on a Grid

What Do You Think?

On a 10 by 10 grid with a wall between start and goal, Dijkstra finds the shortest route and expands 76 cells. A* with the Manhattan distance runs on the same grid. Which result do you expect?

pythonrunnable cell

grid = ["..........",
        "..........",
        "....####..",
        "....#.....",
        "....#.....",
        "....#.....",
        "..........",
        "..........",
        "..........",
        ".........."]


def search(grid, start, goal, scale):
    """Dijkstra when scale is 0, A* with Manhattan distance when scale is 1.

    Returns (cost, cells expanded). Worst case O((V + E) log V) like Dijkstra, space O(V).
    """
    rows, cols = len(grid), len(grid[0])

    def guess(cell):
        return scale * (abs(cell[0] - goal[0]) + abs(cell[1] - goal[1]))

    best = {start: 0}
    heap = [(guess(start), 0, start)]            # (g + h, g, cell)
    expanded = 0
    while heap:
        _, g, cell = heapq.heappop(heap)
        if g > best[cell]:
            continue                              # stale pair
        expanded += 1
        if cell == goal:
            return g, expanded
        r, c = cell
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
                if g + 1 < best.get((nr, nc), INF):
                    best[(nr, nc)] = g + 1
                    heapq.heappush(heap, (g + 1 + guess((nr, nc)), g + 1, (nr, nc)))
    return None, expanded


open_cells = sum(row.count(".") for row in grid)
print("open cells:", open_cells)
print("Dijkstra:", search(grid, (3, 1), (3, 8), 0))
print("A*:      ", search(grid, (3, 1), (3, 8), 1))
# Output:
# open cells: 93
# Dijkstra: (11, 76)
# A*:       (11, 25)

#Which Algorithm? A Decision Table

Ask three questions in order: are all the weights equal, can any be negative, and do you need one source or every pair?

Situation	Use	Time	Why
Every edge costs the same	BFS	O(V + E)	fewest edges is the cheapest route
Edges cost 0 or 1	0-1 BFS	O(V + E)	a deque stands in for the heap
Many starting points, one question	Multi-source BFS	O(V + E)	start the queue with all sources
Weights not negative, one source	Dijkstra	O((V + E) log V)	the heap settles the closest vertex
Not negative, and a good guess to one goal	A*	at most Dijkstra's	the guess skips unhelpful areas
No cycles (a DAG), any weights	Topological order, relax once	O(V + E)	no heap, negatives are fine
Negative edges, one source	Bellman-Ford	O(V·E)	repeated rounds, and it spots negative cycles
Every pair, small graph	Floyd-Warshall	O(V³)	three short loops
Every pair, large sparse graph	Dijkstra from each vertex	V times O((V + E) log V)	cheaper than V³ when E is small

#Where This Shows Up

A route planner models roads as edges with travel times and runs Dijkstra or A* with a map-distance guess. Real services add heavy precomputation on top, but the core question is the one in this lesson.
Internet routers share link costs and compute shortest routes. OSPF, a protocol used inside networks, runs Dijkstra, and the older RIP protocol is built on the Bellman-Ford idea.
Build tools, package managers and CI pipelines use topological sort to decide what to run first, and they report a circular dependency when Kahn's line comes out short.
A project plan is a DAG of tasks. The longest path is the critical path, so a delay on it delays the whole project.
A negative cycle in a table of currency exchange rates (using the negative logarithm of each rate as the weight) is a profit loop. Bellman-Ford finds it.
In speech and language models, Viterbi decoding finds the best sequence of hidden states. It is a shortest path through a DAG of states, solved with the same relax-in-order idea.

#Common Mistakes

Watch Out

Floyd-Warshall with the loops in the wrong order

Fix: Make the middle stop k the outermost loop. Then each pass has finished using the earlier stops everywhere before the next stop is added.

pythonrunnable cell

def floyd_warshall_wrong(vertices, edges):
    dist = {u: {v: (0 if u == v else INF) for v in vertices} for u in vertices}
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
    for i in vertices:                        # k should be out here
        for j in vertices:
            for k in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


wrong = floyd_warshall_wrong(towns, links)
print(wrong["A"]["C"], table["A"]["C"])
# Output:
# 6 4

Watch Out

An A* guess that is bigger than the truth

Fix: Use a guess that never overestimates, like the Manhattan distance on a four-direction grid. If you must overestimate, accept that the route may not be the shortest.

pythonrunnable cell

spiral = ["..........",
          ".########.",
          ".#......#.",
          ".#.####.#.",
          ".#.#..#.#.",
          ".#.#.##.#.",
          "...#......"]

print("scale 0:", search(spiral, (0, 0), (4, 4), 0))
print("scale 1:", search(spiral, (0, 0), (4, 4), 1))
print("scale 10:", search(spiral, (0, 0), (4, 4), 10))
# Output:
# scale 0: (22, 43)
# scale 1: (22, 43)
# scale 10: (26, 33)

#Try It: Five Problems

pythonplayground.py · Pyodide

import heapq
from collections import deque

INF = float("inf")

# 3. Build order. Return the tasks in an order that respects the arrows, or None if there is a cycle.
def build_order(deps):
  # TODO: Kahn's algorithm with in-degrees and a deque
  return None

#Recap

A negative edge breaks the settle step, and a negative cycle means no cheapest path exists.

Topological sort orders a DAG in O(V + E), by Kahn's in-degree queue or by DFS, and it lets you find shortest or longest paths in a DAG without a heap.

Quick Check1 / 6

A graph has edges of weight 1, 2 and 5, and none are negative. You need the cheapest route from one source to every other vertex. Which algorithm fits best?

Recap

Key Takeaways

Shortest means smallest total weight, which is a different question from fewest edges
Dijkstra settles the closest vertex with a heap and skips stale pairs, in O((V + E) log V) time, and it needs non-negative weights
Topological sort exists only for a DAG, costs O(V + E), and a short Kahn result means a cycle
Bellman-Ford costs O(V·E), allows negative edges, and one extra round that still improves means a negative cycle
Floyd-Warshall fills every pair in O(V³) time and O(V²) space, and k must be the outermost loop
Use BFS for equal weights, 0-1 BFS for 0 or 1, and A* only with a guess that never overestimates

Shortest Paths: Dijkstra, Bellman-Ford, A* and More

#The Shortest Path Question

#Recap: BFS Counts Edges, Not Weights

#Dijkstra: Always Settle the Closest Vertex

#Why Dijkstra Needs Non-Negative Weights

#Topological Sort: Kahn and DFS

#Shortest and Longest Paths in a DAG

#Bellman-Ford: Negative Edges and Negative Cycles

#Floyd-Warshall: All Pairs

#0-1 BFS and Multi-Source BFS

#A* Search on a Grid

#Which Algorithm? A Decision Table

#Where This Shows Up

#Common Mistakes

#Try It: Five Problems

#Recap

Your Reflection

Continue Learning

Discussion

Shortest Paths: Dijkstra, Bellman-Ford, A* and More

#The Shortest Path Question

#Recap: BFS Counts Edges, Not Weights

#Dijkstra: Always Settle the Closest Vertex

#Why Dijkstra Needs Non-Negative Weights

#Topological Sort: Kahn and DFS

#Shortest and Longest Paths in a DAG

#Bellman-Ford: Negative Edges and Negative Cycles

#Floyd-Warshall: All Pairs

#0-1 BFS and Multi-Source BFS

#A* Search on a Grid

#Which Algorithm? A Decision Table

#Where This Shows Up

#Common Mistakes

#Try It: Five Problems

#Recap

Your Reflection

Continue Learning

Discussion