Dijkstra's Algorithm and A* Search

Dijkstra's shortest path algorithm

In a weighted graph every edge has a cost, such as a distance, a time or a price. The shortest path between two vertices is the one with the lowest total weight, which is not necessarily the one with the fewest edges. Breadth first search counts edges. Dijkstra's algorithm counts weights.

It finds the shortest distance from one start vertex to every other vertex, as long as no weight is negative. It works by always fixing the nearest vertex that is not yet fixed, and then seeing whether that vertex gives a shorter way to any of its neighbours.

The method, which the exam expects you to be able to carry out by hand:

1. Give the start vertex a distance of 0 and every other vertex a distance of infinity.
2. Choose the unfixed vertex with the smallest distance and fix it. That distance is now final.
3. For each neighbour of that vertex, work out distance of the vertex plus the edge weight. If that is smaller than the neighbour's recorded distance, replace the distance, and record that the neighbour was reached from this vertex.
4. Repeat from step 2 until every vertex is fixed, or until the goal is fixed.

Step 2 is "find the smallest of the waiting vertices", and a priority queue does exactly that. Python's heapq is one.

import heapq

graph = {
    "A": {"B": 7, "C": 9, "F": 14},
    "B": {"A": 7, "C": 10, "D": 15},
    "C": {"A": 9, "B": 10, "D": 11, "F": 2},
    "D": {"B": 15, "C": 11, "E": 6},
    "E": {"D": 6, "F": 9},
    "F": {"A": 14, "C": 2, "E": 9},
}

def dijkstra(graph, start):
    distance = {v: float("inf") for v in graph}
    previous = {v: None for v in graph}
    distance[start] = 0
    queue = [(0, start)]
    fixed = []
    while queue:
        dist, vertex = heapq.heappop(queue)
        if vertex in fixed:
            continue                                  # an out of date entry
        fixed.append(vertex)
        for neighbour, weight in graph[vertex].items():
            new = dist + weight
            if new < distance[neighbour]:
                distance[neighbour] = new
                previous[neighbour] = vertex
                heapq.heappush(queue, (new, neighbour))
        row = [distance[v] for v in graph]
        print("fixed", vertex, row)
    return distance, previous

def path_to(previous, goal):
    path = []
    while goal is not None:
        path.append(goal)
        goal = previous[goal]
    return path[::-1]

distance, previous = dijkstra(graph, "A")
print(path_to(previous, "E"), distance["E"])

The lines printed are the rows of the working table the exam asks for, with the columns in the order A, B, C, D, E, F:

Step 3 is the one that shows the method working. When C is fixed at 9, the route to D through C costs 9 + 11 = 20, which beats the 22 found through B. The route to F through C costs 9 + 2 = 11, which beats the direct edge of 14. The bold values are distances that were improved.

Why a negative weight breaks it

Dijkstra's algorithm is greedy. When it fixes a vertex, it assumes no later route can be shorter, because every later route has to go through vertices that are further away and can only add. A negative edge could subtract, making an apparently longer route into a shorter one after the vertex was already declared final.

How much work

With a heap, each edge causes at most one push, and each push or pop costs the logarithm of the heap's size. The total is about (V + E) log V steps, where V is the number of vertices and E the number of edges. That is fast enough for a road network of millions of junctions.

A* search

Dijkstra's algorithm spreads out from the start in every direction, like a ripple, and fixes every vertex nearer than the goal. If you are navigating from Manchester to Leeds, that includes vertices in Wales. A* (say "A star") avoids this by being guided: it prefers vertices that look as if they are heading towards the goal.

For each vertex n it uses two numbers:

• g(n): the real cost of the best route found so far from the start to n
• h(n): a heuristic, an estimate of the cost still to go from n to the goal

and it always expands the vertex with the smallest f(n) = g(n) + h(n), the estimated cost of the whole journey through n. Dijkstra's algorithm is exactly A* with h = 0 for every vertex.

The heuristic

A heuristic is a rule of thumb: a quick estimate that need not be exact. For finding a route across a map, the straight line distance to the goal is a natural one. On a grid where you can move up, down, left and right, it is the Manhattan distance, the number of rows plus the number of columns still to travel.

For A* to be certain to find the shortest path, the heuristic must be admissible: it must never overestimate the true remaining cost. The Manhattan distance is admissible on this grid, because you can never get there in fewer moves than the rows plus columns, and walls can only make it longer. A heuristic that overestimated could make the best route look too expensive, and A* would pass it over.

Dijkstra and A* on the same grid

Both programs below are the same code. The only difference is whether h is 0 or the Manhattan distance. o marks every cell that was expanded, and * is the path found. Ties in f are broken in favour of the smaller h, which keeps A* heading for the goal.

import heapq

GRID = [
    "S.........",
    "..........",
    "..........",
    "......#...",
    "......#...",
    "......#...",
    "......#...",
    "..........",
    "..........",
    ".........G",
]

def search(grid, start, goal, use_heuristic):
    rows, cols = len(grid), len(grid[0])

    def h(cell):
        if not use_heuristic:
            return 0
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])

    best = {start: 0}
    previous = {start: None}
    queue = [(h(start), h(start), 0, start)]
    expanded = []
    while queue:
        f, estimate, g, cell = heapq.heappop(queue)
        if cell in expanded:
            continue
        expanded.append(cell)
        if cell == goal:
            break
        row, col = cell
        for step_row, step_col in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            r, c = row + step_row, col + step_col
            if 0 <= r < rows and 0 <= c < cols and grid[r][c] != "#":
                new_g = g + 1
                if new_g < best.get((r, c), 10 ** 9):
                    best[(r, c)] = new_g
                    previous[(r, c)] = cell
                    heapq.heappush(queue, (new_g + h((r, c)), h((r, c)), new_g, (r, c)))
    path = []
    cell = goal
    while cell is not None:
        path.append(cell)
        cell = previous[cell]
    return expanded, path[::-1]

for name, use_h in (("Dijkstra", False), ("A*", True)):
    expanded, path = search(GRID, (0, 0), (9, 9), use_h)
    canvas = [list(line) for line in GRID]
    for row, col in expanded:
        if canvas[row][col] == ".":
            canvas[row][col] = "o"
    for row, col in path[1:-1]:
        canvas[row][col] = "*"
    print(name, "expanded", len(expanded), "cells; path of", len(path) - 1, "steps")
    for line in canvas:
        print("".join(line))

Both find a path of 18 steps, which is the shortest possible. Dijkstra's algorithm had to look at 96 cells to prove it, and A* looked at 19.

Choosing between the three

Dijkstra's algorithm answers "how far is it to everywhere?" A* answers "what is the best route to this place?", and gets there faster by using what it knows about where the goal is.

Key terms you must be able to define

Shortest path

The route between two vertices of a weighted graph with the lowest total weight.

Dijkstra's algorithm

An algorithm that finds the shortest distance from a start vertex to every other vertex in a graph with non-negative weights.

Priority queue

A queue from which the item with the highest priority, here the smallest distance, is always removed first.

Greedy algorithm

An algorithm that makes the best looking choice at each step, without reconsidering it.

A* search

A shortest path algorithm that uses a heuristic to prefer vertices that appear to lead towards the goal.

Heuristic

An estimate or rule of thumb that is quick to calculate and need not be exact.

Admissible heuristic

A heuristic that never overestimates the true cost of reaching the goal.

g(n)

In A*, the cost of the best known route from the start to vertex n.

h(n)

In A*, the heuristic estimate of the cost from vertex n to the goal.

Manhattan distance

The distance between two points on a grid measured as rows plus columns, as when moving only up, down, left and right.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

Shortest path questions are marked on method shown in a table, and on being exact about the difference between the two algorithms.

• Set up the working table with infinity for every vertex but the start, and update a row per fixed vertex
• Only replace a distance when the new total is strictly smaller, and record where it came from
• Write the path backwards from the goal using the recorded previous vertices, then reverse it
• State A* as f = g + h and name g as cost so far and h as the estimate still to go
• Say that an admissible heuristic never overestimates, and that this is what guarantees the shortest path

Mistakes that cost marks here