Dijkstra's shortest path algorithm

Tracing Dijkstra's algorithm in a table, why negative weights break it, a priority queue version, its efficiency and applications.

A5.7Algorithms and complexityA level30 min

In module A4 you met weighted graphs and breadth-first search. Breadth-first search finds the route with the fewest edges, which is only the shortest route when every edge costs the same. On the mat the roads between zones have different lengths, so the robot needs the route with the smallest total weight. Dijkstra's algorithm finds it.

From A to F, one route with the fewest roads is A, B, D, F (3 roads, 4 + 5 + 6 = 15). Is there a shorter one? Checking every route by hand gets slow quickly. Dijkstra's algorithm answers it for every vertex at once, without trying every route.

The algorithm

Dijkstra's algorithm finds the shortest distance from one start vertex to every other vertex, in a graph whose weights are not negative. For each vertex it keeps a distance (the shortest found so far) and a previous vertex (where that route arrived from).

1. Set every distance to infinity, and the start vertex's distance to 0. Mark every vertex unvisited.
2. Choose the unvisited vertex with the smallest distance, and mark it visited. Its distance is now final.
3. For each unvisited neighbour of that vertex: work out the distance to it through this vertex (this vertex's distance plus the edge weight). If that is smaller than the neighbour's current distance, replace the distance, and set the neighbour's previous vertex to this vertex.
4. Repeat from step 2 until every vertex is visited (or, if you only need one destination, until it is visited).

Then read the route backwards: start at the destination and follow the previous vertices back to the start.

A trace

Each row shows the distances after visiting one vertex, written as distance (previous). A bold entry is visited, so it is final.

Look at the key moments:

• Step 2: C is visited before B because its distance (2) is smaller. Going A, C, B costs 2 + 1 = 3, which beats the direct road A, B at 4, so B's entry changes to 3 (C).
• Step 4: from D, E costs 8 + 2 = 10, better than the 12 found through C.
• Step 5: from E, F costs 10 + 3 = 13, better than the 14 through D.

Reading back from F: F came from E, E from D, D from B, B from C, C from A. The shortest route is A, C, B, D, E, F, length 13. It uses five roads, not three: fewest roads is not shortest distance.

Why it works, and when it does not

Dijkstra's algorithm is greedy: at each step it takes the closest unvisited vertex and never reconsiders it. That is safe because every other unvisited vertex is already at least as far away, and with no negative weights, going through one of them can only add distance. So the closest one's distance cannot be improved.

With a negative weight that argument breaks. In a directed graph with A to B weighing 2, A to C weighing 3 and C to B weighing -2, the algorithm visits B first and fixes its distance at 2, but A, C, B costs 3 - 2 = 1. Dijkstra's algorithm must only be used when no weight is negative (road lengths and travel times never are).

In Python

The step "choose the unvisited vertex with the smallest distance" is exactly what a priority queue does (module A3). Python's heapq module keeps a list as a priority queue: heappop always removes the smallest item.

import heapq

roads = {
    "A": {"B": 4, "C": 2},
    "B": {"A": 4, "C": 1, "D": 5},
    "C": {"A": 2, "B": 1, "D": 8, "E": 10},
    "D": {"B": 5, "C": 8, "E": 2, "F": 6},
    "E": {"C": 10, "D": 2, "F": 3},
    "F": {"D": 6, "E": 3},
}

def dijkstra(graph, start):
    distance = {v: float("inf") for v in graph}
    previous = {v: None for v in graph}
    distance[start] = 0
    visited = set()
    queue = [(0, start)]                             # (distance, vertex) pairs
    while queue:
        dist, vertex = heapq.heappop(queue)          # the closest vertex still waiting
        if vertex in visited:
            continue                                 # an old, longer entry: skip it
        visited.add(vertex)
        for neighbour, weight in graph[vertex].items():
            new = dist + weight
            if neighbour not in visited and new < distance[neighbour]:
                distance[neighbour] = new
                previous[neighbour] = vertex
                heapq.heappush(queue, (new, neighbour))
    return distance, previous

def route(previous, end):
    path = []
    while end is not None:
        path.append(end)
        end = previous[end]
    return path[::-1]                                # it was built backwards

distance, previous = dijkstra(roads, "A")
print(distance)
print("A to F:", route(previous, "F"), distance["F"])

Run this in the simulator

When a shorter distance is found, the vertex is pushed again rather than updated in place, so a vertex can be in the queue more than once. The longer copy comes out later and is skipped because the vertex is already visited.

Efficiency

With V vertices and E edges:

• Finding the closest unvisited vertex by scanning a list costs O(V) each time, and it happens V times: O(V²) overall.
• With a binary heap as the priority queue each push and pop costs O(log V), giving O((V + E) log V), much better for large graphs where each vertex has only a few edges, such as road maps.

Either way it is polynomial. Compare that with trying every route, which grows factorially.

Where it is used

• Satellite navigation and map apps: junctions are vertices, roads are edges weighted by distance or expected time.
• Network routing: in link-state routing protocols such as OSPF, each router builds a map of the network and runs Dijkstra's algorithm to find the lowest-cost path to every other network.
• Robots and games: planning a route across a map of waypoints, as BugBot does in this module's project.
• Logistics: delivery and transport planning, where weights can be distance, time or cost.

Task: the shortest route table

roads in the starter is the graph above as a dictionary of dictionaries (an adjacency list with weights). Write dijkstra(graph, start) that returns two dictionaries, the shortest distance to each vertex and the previous vertex on that route (None for the start). Run it from A and print one line per vertex, in alphabetical order, in exactly this form, <vertex>: <distance> from <previous vertex>, for example:

X: 12 from Y

with A: 0 from - for the start. Then follow the previous vertices back from G and print the route and its length:

route A to G: <vertices joined with ->, cost <n>

such as route A to G: A-X-Y-G, cost 20. The program must find the route: do not type it.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

roads = {
    "A": {"B": 7, "C": 3},
    "B": {"A": 7, "C": 2, "D": 4},
    "C": {"A": 3, "B": 2, "D": 8, "E": 6},
    "D": {"B": 4, "C": 8, "E": 1, "F": 5},
    "E": {"C": 6, "D": 1, "F": 9, "G": 12},
    "F": {"D": 5, "E": 9, "G": 2},
    "G": {"E": 12, "F": 2},
}

Challenges

1. Trace the task's graph by hand in a table before you run your program. Where did you have to change an entry?
2. Make the road from D to F one-way (D to F only). Does the answer change? Why not?
3. Change dijkstra so it stops as soon as the destination is visited. How many vertices does it visit on the way to D?