Shortest Paths

General

The distance of two nodes $u, v$ , denoted $dist (u, v)$ , in an unweighted directed graph $G = (V, E)$ is defined as the shortest length of a walk from $u$ to $v$ .

The cost of an edge $e = (u, v) \in E$ , denoted $c (e) \in R$ , in a weighted graph $G = (V, E)$ is the weight of said edge. The cost of a walk $W = (v_{0}, v_{1}, \dots, v_{l})$ from vertex $v_{0}$ to $v_{l}$ is defined as the sum of the cost of each incident edge in the walk, i.e., $c (W) = c ((v_{0}, v_{1})) + \dots + c ((v_{l - 1}, v_{l}))$ .

Notation:

$u \to e v$ if $e = (u, v) \in E$
$u ⇝ W v$ if $W$ is a walk from $u$ to $v$

The distance of two nodes $u, v$ , denoted $dist (u, v)$ , is in such a graph defined as $dist (u, v) = min {c (W) ∣ u ⇝ W v}$ .

DP for DAGs

The shortest path problem is a DP problem in directed acyclic graphs, with the following recurrence: $dist (s, v) = min_{u, v \in E} dist (s, u) + c (u, v)$ . It can be computed in $O (∣ V ∣ + ∣ E ∣)$ .

Breadth-First Search (BFS)

Runtime

$O (∣ V ∣ + ∣ E ∣)$

Pseudocode

def bfs(s, graph):
    q = Queue(s)
    dist = [None] * len(graph.nodes)
    enter = [None] * len(graph.nodes)
    leave = [None] * len(graph.nodes)
    dist[s] = 0
    enter[s] = 0
    t = 1
    while !q.isEmpty():
        u = q.dequeue()
        leave[u] = t
        t = t + 1
        for v in u.children:
            if !enter[v]:
                q.enqueue(v)
                dist[v] = dist[u] + 1
                enter[v] = t
                t = t + 1
    return dist

Further Resources

Breadth-first search - Wikipedia

Dijkstra’s Algorithm

Single-source shortest path algorithm for arbitrary graphs with non-negative weights.

Runtime

$O ((∣ V ∣ + ∣ E ∣) \cdot lo g (∣ V ∣))$

Pseudocode

import math

def dijkstra(s, graph):
    dist = [math.inf] * len(graph.nodes)
    dist[s] = 0
    prev = [None] * len(graph.nodes)
    pq = MinPriorityQueue()
    for v in graph.vertices:
        pq.addWithPriority(v, dist[v])
    while !pq.isEmpty():
        u = pq.extractMin()
        for v in u.children:
            alt = dist[u] + cost(u, v)
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                pq.decreasePriority(v, alt)
    return dist, prev
        

Further Resources

Dijkstra’s algorithm - Wikipedia

Bellman-Ford Algorithm

Single-source shortest path algorithm for arbitrary directed graphs without the restriction on non-negative weights. It can detect negative-weight cycles and report them.

Runtime

$O (∣ V ∣ \cdot ∣ E ∣)$

Pseudocode

import math

def bellman_ford(s, graph):
    dist = [math.inf] * len(graph.vertices)
    prev = [None] * len(graph.vertices)
    dist[s] = 0
    for i in range(len(graph.vertices) - 1):
        for (u, v, w) in graph.edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    for (u, v, w) in graph.edges:
        if dist[u] + w < dist[v]:
            raise NegativeWeightCycleException()
    return dist, prev

Further Resources

Bellman-Ford algorithm - Wikipedia

Comparing Single-Source Shortest Path Algorithms

Single-Source Shortest Path Algorithms

Floyd-Warshall Algorithm

All-pairs shortest path algorithm for graphs without negative cycles.

Runtime

$O (∣ V ∣^{3})$

Pseudocode

import math

def floyd_warshall(graph):
    dist = [None] * len(graph.vertices)
    for i in range(len(graph.vertices)):
        dist[i] = [None] * len(graph.vertices)
        for j in range(len(graph.vertices)):
            dist[i][j] = [math.inf] * len(graph.vertices)
    for u in graph.vertices:
        dist[0][u][u] = 0
    for (u, v, c) in graph.edges:
        dist[0][u][v] = c
    for i in range(1, len(graph.vertices)):
        for u in range(1, len(graph.vertices)):
            for v in range(1, len(graph.vertices)):
                dist[i][u][v] = min(dist[i - 1][u][v], dist[i - 1][u][i] + dist[i - 1][i][v])
    return dist

Further Resources

Floyd-Warshall algorithm - Wikipedia

Johnson’s Algorithm

All-pairs shortest path algorithm.

Idea: Make all edge weights positive and execute Dijkstra $∣ V ∣$ -times. This is done by adding a new vertex $q$ with an edge with weight 0 to every other vertex. In order to not change the shortest paths in this new graph all edges must be re-weighted according to the following function: $\overset{w}{^} (u, v) = w (u, v) + h (u) - h (v)$ where $h (u)$ is the length of the shortest path in the new graph from $q$ to $u$ . Then $q$ is removed and Dijkstra is executed for every node.

Runtime

$O (∣ E ∣ \cdot ∣ V ∣ + ∣ V ∣^{2} \cdot lo g n)$

Pseudocode

def johnson(graph):
    dist = [None] * len(graph.vertices)
    for i in range(len(graph.vertices)):
        dist[i] = [None] * len(graph.vertices)
    graph.vertices.append(-1)
    for i in range(len(vertices))
        graph.edges.append(-1, i, 0)
    h = bellman_ford(-1, graph)
    for u in graph.vertices:
        for (u, v, w) in graph.edges:
            w = w + h[u] - h[v]
    for u in graph.vertices:
        dist[i] = dijkstra(i, graph)
    return dist

Further Resources

Johnson’s algorithm - Wikipedia

Further Resources

Shortest path problem - Wikipedia