If a graph is unweighted (edges do not have weights), we can assume that all edges have weight 1. If all edges have the same weight, we can do a breadth-first search starting at a source node $s$ to find the shortest paths to all other nodes.

Dijkstra’s algorithm finds the shortest path tree (SPT) that stores the shortest paths from a single source vertex $s$ to all other vertices.

Dijkstra’s algorithm uses relaxation. For each vertex $v$, we maintain its distance v.distance from the source as an upper bound (shortest-path estimate aka current best-known distance) and its predecessor v.predecessor.

initSingleSource(Graph, source):
    for each vertex v ∈ Graph.vertices:
        v.distance = ∞
        v.predecessor = nil
    source.distance = 0

The process of relaxing and edge $e = (v, w)$ consists of testing whether we can improve the shortest path from source $s$ to $w$ found so far by going through the vertex $v$ and, if so, updating w.distance and w.predecessor:

relax(e):
    v = e.source
    w = e.target
    currentBestKnownWeight = w.distance
    possiblyBetterWeight = v.distance + e.weight
    if possiblyBetterWeight < currentBestKnownWeight
        w.distance = possiblyBetterWeight
        w.predecessor = v

Pseudocode for Dijkstra’s algorithm:

Dijkstra(Graph, source):
    initSingleSource(Graph, source)
    while not every vertex is part of tree:
        v = vertex with smallest distance and not in tree
        v.partOfTree = true
        for each edge e of v:
            relax(e)

Runtime is $O(|V| \log |V| + |V| \log |V| + |E| \log |V|)$, and since $E > V$ for any graph on which we wound run Dijkstra’s algorithm, we can more simple write the complexity as $O(|E| \log |V|)$.

Visualization:

Like Dijkstra’s algorithm, Bellman–Ford algorithm solves the single-source shortest path problem, but also works with graphs where some edge weights are negative.

Note that we did not cover Bellman–Ford algorithm in EECS 281 this semester.

If we only need to find a path from a single source to a single target, then Dijkstra’s algorithm is inefficient, as it explores many edges that we do not care about.

For example, suppose you would like to find the shortest path from Ann Arbor to Chicago, then it would not make sense to explore paths longer that ~300 miles in all direction before reaching Chicago.

To fix this, we make a very minor change to Dijkstra’s algorithm: instead of visiting vertices in order of distance from the source, we visit them in order of distance from the source + $h(v)$, where $h(v)$ is some heuristic.

Note that we did not cover the A* algorithm in EECS 281 this semester.

Floyd–Warshall algorithm solves the all-pairs shortest path problem. Negative-weight edges may be present, but we assume that there are no negative-weight cycles.

First, let’s start with a simple example of a graph.

Floyd–Warshall algorithm algorithm breaks the all-pairs shortest path problem into subproblems that can be easily solved using dynamic programming. We start by letting $T^0(i,j)$ be the length of the shortest direct path (of length ≤ 1) from $i$ to $j$. It is equal to the length of the edge $(i, j)$ if it exists and ∞ otherwise. We set $T^0(i,i) = 0$ for all $i$.

We define the problem $T^k(i, j)$ as the shortest path from $i$ to $j$ that is only allowed to use the first $k$ vertices as intermediate vertices (numbered from $0$ to $k - 1$). For example, $T^1(i,j)$ is the shortest path from $i$ to $j$ that is either $i \rightarrow j$ or $i \rightarrow 0 \rightarrow j$. $T^2(i,j)$ is the shortest path from $i$ to $j$ that is either $i \rightarrow j$, $i \rightarrow 0 \rightarrow j$, $i \rightarrow 1 \rightarrow j$, $i \rightarrow 0 \rightarrow 1 \rightarrow j$ or $i \rightarrow 1 \rightarrow 0 \rightarrow j$.

We now need to define the problem $T^k(i, j)$ in terms of $T^{k - 1}$ in order to use dynamic programming. Suppose we want to find the shortest path from $i$ to $j$ that uses the first $k$ vertices (up to $k - 1$) as intermediate vertices. There are two cases:

We can write the recursive definition for the algorithm as $T^k(i, j) = \min( T^{k - 1}(i, j), T^{k - 1}(i, k) + T^{k - 1}(i, k))$.

Pseudocode:

FloydWarshall(Graph):
    for each vertex v in Graph.V:
        dist[v][v] = 0
    for each edge e in Graph.E:
        v = e.source
        w = e.target
        dist[v][w] = e.weight
    for k = 0 ... |Graph.V| - 1:
        for i = 0 ... |Graph.V| - 1:
            for j = 0 ... |Graph.V| - 1:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

When we implement the Floyd–Warshall algorithm, we want to keep track of distances and predecessor, similarly to Dijkstra’s algorithm. However, here we use two 2D arrays for that purpose, instead of two 1D arrays.

Here is a visualization of the Floyd–Warshall algorithm.