Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Shortest Path Problem

Given a weighted graph and two vertices and , find a path between them with the minimum total weight. The length of a path is the sum of its edge weights, also called the distance between the two vertices. There can be several shortest paths. Applications include flight routing with no direct flight, Internet packet routing and driving directions.

Shortest Path Tree

A shortest path tree (SPT) is formed by the shortest paths from one start vertex to all other vertices:

  • from any start vertex these shortest paths always form a tree
  • if several paths to a vertex share the same shortest length, the SPT includes only one of them
  • so a start vertex can have more than one SPT

Algorithm

Input: graph with non-negative weights and a start vertex .

  • add to an empty SPT
  • repeat until the SPT contains every vertex reachable from : add the one vertex (and its edge) not yet in the SPT that extends the paths from as short as possible

This is a greedy rule that is guaranteed to be optimal. The SPT always remains a tree while the algorithm runs.

Example

Edges: (2), (6), (7), (8), (4), (2), (3), start .

StepVertex addedDistanceViaCandidates (distance)
100start
21201 (2), 2 (6)
32602 (6), 3 (9), 5 (10)
43913 (9 via 1, 10 via 2), 5 (10)
551014 (11), 5 (10)
641134 (11 via 3, 13 via 5)

A second example with source builds the table of shortest paths one row at a time, always taking the next shortest:

Python with a Priority Queue

A priority queue (heapq, a minheap) replaces the FIFO queue of BFS: the entry with the shortest distance comes out first.

import heapq
 
def dijkstra(graph, src):                # graph: {u: {v: weight}}
    dist = {v: float('inf') for v in graph}
    parent = {v: -1 for v in graph}
    dist[src] = 0
    pq = [(0, src)]
    visited = set()
    while pq:
        d, u = heapq.heappop(pq)         # closest vertex not yet fixed
        if u in visited:
            continue
        visited.add(u)                   # u joins the SPT
        for v, w in graph[u].items():
            if v not in visited and d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u            # SPT edge
                heapq.heappush(pq, (dist[v], v))
    return dist, parent

For the example graph this returns distances 0, 2, 6, 9, 11, 10 for vertices 0 to 5 and parents 1:0, 2:0, 3:1, 4:3, 5:1.

Dijkstra versus BFS and DFS

CriteriaDijkstraBFS / DFS
Main objectivefind the fastest routefind the fastest route
Edge weights neededyesno
Goalfixed start and end pointsanything you want to find
MRT examplesmallest total travel time (edge weights)fewest interchange stations (count nodes)

BFS gives the fewest edges, which is the shortest path only when all edges have equal weight.