10. Cheapest Paths

Dijkstra

Shortest path between source node and all other nodes in a graph with no negative edges.

How it works: Always look at the node with the lowest distance from the start node. Repeat this until all nodes have been relaxed (or shortcut once your goal node is visited).

Why it works: All other unvisited nodes must have an optimal distance as high (if edge has weight $0$) or higher than the lowest unvisited node. You cannot make up distance without neg. edges (triangle inequality).

public static int dijkstra(int s, int t, int n, int[][] E, int[][] W) {
    int[] dist = new int[n];
    
    for (int i=0; i<n; i++) dist[i] = Integer.MAX_VALUE / 2;
    
    record Key(int node, int dist) {}
    Queue<Key> pq = new PriorityQueue<>(
        (a, b) -> Integer.compare(a.dist, b.dist)
    );
	
    dist[s] = 0;
    pq.add(new Key(s, 0));
    
    while (!pq.isEmpty()) {
        Key curr = pq.poll();
        
        if (curr.dist != dist[curr.node]) continue;
        if (curr.node == t) break;
        
        for (int i=0; i<E[curr.node].length; i++) {
            int adjNode = E[curr.node][i];
            int newDist = curr.dist + W[curr.node][i];
            if (newDist < dist[adjNode]) {
                dist[adjNode] = newDist;
                pq.add(new Key(adjNode, newDist));
	        }
        }
    }
    
    return dist[t];
}

Runtime Binary Heap

• You iterate over all nodes and always extract the min from the binary heap $⟹$ $\mathcal{O}(V\log V)$
• Each time you iterate over a node, you iterate over all incident edges. That equals all edges $E$ in total. In the worst case, you have to decrease the key of all $E$ edges (or insert a duplicate key), which costs $\log V$ (updating the dist array is $O(1)$) $⟹$ $\mathcal{O}(E\log V)$.

Total: $\mathcal{O}(V\log V+E\log V)=\mathcal{O}((V+E)\log V)$

Runtime Standard Array

While there are still unvisited nodes (totals $V$ iterations):

• You first iterate over all $V$ distances to find the min
• You then iterate over all incident edges to decrease their entry in the distances array. That equals all edges $E\le V^2$ across all $V$ runs.

Total: $\mathcal{O}(V^2+V^2)=\mathcal{O}(V^2)$

Dijkstra can also be impl. using a Fibonacci Heap in $\mathcal{O}(V\log V+E)$ since decrease-key is amortized $\mathcal{O}(1)$. However, it rarely used due to its high constant factors, cache inefficiency, and complex implementation.

Aside: A*

A* is Dijkstra + a heuristic function $h(n)$ to estimate the remaining cost from node $n$ to the goal. It typically expands fewer nodes than Dijkstra by prioritizing directions that “look” promising.

Instead of selecting the node with the smallest $\text{dist}[n]$, A* selects the node minimizing $f(n)=\text{dist}[n]+h(n)$. When $h(n)=0$ for all nodes, A* reduces to Dijkstra. We stop once we found the target.

If $h$ is admissible (never overestimates the true remaining cost) and consistent ($h(n)\le w(n,n^{\prime })+h(n^{\prime })$ for every edge), A* is guaranteed to find the optimal shortest path: all nodes coming after must be further away since going through all others must take longer (heuristic is lower bound).

Bellman-Ford

Shortest path between source node and all other nodes in a graph with negative edges.

How it works: Go over all nodes. Relax all adjacent nodes. Repeat $V-1$ times or until no improvement can be made.

Why this works: The shortest path between the start node and any other node can have at most $V-1$ edges. As a shortest path, there exists no shorter path to any of the nodes on the way — otherwise, the path could be abbreviated. Since it starts at the source, the path is extended by one edge every cycle.

Negative cycles: $\exists$ negative cycle $⟺$ any node’s distance improves between $V-1$ and $V$ iterations.

Runtime

• We iterate $V-1$ times
• Each time, we iterate over all $E$ edges, always by iterating over all nodes and looking at the adjacent ones.

Total: $\mathcal{O}((V-1)\cdot E)=\mathcal{O}(V\cdot E)$

Floyd-Warshall

Shortest path between every node and every other nodes in a graph with negative edges. DP algorithm.

State: $\text{dist}[k][i][j]$ = length of path from $i$ to $j$ using the first $k$ nodes as possible intermediaries.

Base case:

$$\text{dist}[0][i][j]=\{\begin{array}{ll}0& \text{if }i=j\\ w((i,j))& \text{if }(i,j)\in E\\ \infty & \text{otherwise}\end{array}$$

Recurrence: $\text{dist}[k][i][j]=\min (\underset{\text{reuse prev. sol}}{\underbrace{\text{dist}[k-1][i][j]}},\underset{\text{route through }k}{\underbrace{\text{dist}[k-1][i][k]+\text{dist}[k-1][k][j])}}$ At each step, we check if routing through a new intermediary node results in a better result.

Calculation order: Since every entry relies on entries that may be in anywhere in the $k-1$-th layer, we must compute the entire $k-1$-th before the $k$-th layer. In practice, this involves nesting the $i$ and $j$ loops inside the $k$ loop.

Optimization: Our recurrence only relies on the $k-1$-th layer. We can therefore optimize our space usage by updating our recurrence: $\text{dist}[i][j]$ $=\min (\text{dist}[i][j],\text{dist}[i][k]+\text{dist}[k][j])$. We keep the order of the three for loops.

$\text{dist}[i][k]$ and $\text{dist}[k][j]$ corresponds to $\text{dist}[i][k][k-1]$ and $\text{dist}[k][j][k-1])$ b/c, by definition, a path starting or ending in $k$ cannot use $k$ as intermediary node; it wouldn’t be a path then.

Runtime

• You iterate over $V$ with 3 nested loops
• Each time, you find the minimum and update an array entry in $\mathcal{O}(1)$

Total: $\mathcal{O}(V^3)$

If there ex. no negative edges and $\mathcal{O}(E)<\mathcal{O}(V^2)$, running Dijkstra $V$ times is faster: $\mathcal{O}(V(E+V)\log V)$ vs. $\mathcal{O}(V^3)$

Johnson

Shortest path between every node and every other nodes in a graph with negative edges.

How it works:

• Create a supernode $h$
• Create an edge from $h$ to all other nodes of weight $0$
• Compute distance from $h$ to every other node using Bellman Ford
• Update every weight to $w^{\prime }(u,v)=w(u,v)+h(u)-h(v)$
• Run Dijkstra from every node to every other node

Why it works:

• Updated weights are pos The triangle inequality $h(v)\le w(u,v)+h(u)$ must hold $⟹0\le w(u,v)+h(u)-h(v)$ $⟹$ all $w^{\prime }(u,v)$ are positive
• Path lengths stay the same The shortest path from $a$ to $b$ using $w^{\prime }$ is the same as using $w$ b/c every total path weight equals the sum of the original weights along the path plus $h(a)-h(b)$. All the other heights cancel out.

Runtime

• $\mathcal{O}(1)$ for creating supernode $h$
• $\mathcal{O}(V)$ for creating 0-edges from $h$
• $\mathcal{O}(V\cdot E)$ for Bellman Ford
• $\mathcal{O}(E)$ for updating all weights
• $\mathcal{O}(V\cdot (V+E)\log V)$ for running Dijkstra

Total: $\mathcal{O}(V\cdot (V+E)\log V)$