4. Paths in Graphs

Note: Many chapters of the book are omitted here, as I felt they were too simple to be discussed in depth in an Advanced Algorithms class.

4.4 Dijkstra's Algorithm

Priority queue with 4 operations:

Insert: add a new element in sorted order
Decrease-key: decrease the key value of a particular element, changing its position in the queue if necessary (can also be simulated by reinserting into the priority queue and keeping track of visited nodes)
Delete-min: pop the element with the smallest key
Make-queue: build a priority queue out of the given elements (faster operation than one-by-one insertion)

DPV Psuedocode:

procedure dijkstra(G,l,s):

Input:
- Graph G=(V,E), directed or undirected
- l = set of edges, positive lengths/weights
- s = start vertex
  
Output:
- dist array, where dist[u] is the distance from s to u
  
Algorithm:
for u in V:
	dist[u] = INFTY
	prev[u] = nil
dist[s] = 0

q = makequeue(V)
while !empty(q):
	u = deletemin(H)
	for edge (u,v) in E:
		if dist[v] > dist[u] + l[(u,v)]:
			dist[v] = dist[u] + l[(u,v)]
			prev[v] = u
			decreasekey(q, v)

Proving Dijkstra's algorithm can be done via induction, with the following inductive hypothesis:

At the end of each iteration of the while loop, the following conditions hold:

There is a value $d$ such that $\forall x \in R$ , the set of nodes with known distances, $\mathrm{dist}[x]\leq d$ .

$\forall x \in V$ , the value $\mathrm{dist}[u]$ is the length of the shortest path from $s$ to $u$ whose intermediate nodes are constrained to be in $R$ . If no such path exists, the value is $\infty$ .

Dijkstra's algorithm has a runtime of $O((\lvert V \rvert+\lvert E \rvert)\log \lvert V \rvert)$ with a binary heap. With a Fibonacci heap, this can be improved to $O(\lvert V \rvert \log \lvert V \rvert+\lvert E \rvert)$ . This is optimal for sparse graphs, i.e. when $\lvert E \rvert$ is fairly small.

4.5 Priority Queue Implementations

Array

$O(1)$ for insert and decreasekey. But, deletemin is $O(n)$ .

Binary Heap

Recall 61B! $O(\log n)$ for decreasekey, insert, and deletemin due to "bubbling up" for the first two and "sifting down" for the third.

$d$ -ary Heap

A $d$ -ary heap is just a binary heap except each node has $d$ children. This reduces the height of a tree to $\Theta(\log_{d}n)=\Theta\left( \frac{\log n}{\log d} \right)$ . insert and decreasekey therefore take $O\left( \frac{\log n}{\log d} \right)$ . But, deletemin take $O(d\log_{d}n)$ , since $d$ children must be checked while sifting down.

4.6 Shortest Path Algorithms with Negative Edges

Bellman-Ford

Dijkstra's algorithm does not work with graphs that have negative edge weights. This is because Dijkstra relies on the assumption that the dist values are always $\geq$ the actual distance, and should eventually all converge to the real distance—at which point, they are considered to have be part of the "known" set of nodes.

With negative edges, this is not necessarily true, as the subsequent discovery of a negative edge might mean there exists a shorter path for a node that is already included in the "known" set of nodes.

The Bellman-Ford algorithm is an $O(\lvert V \rvert \cdot \lvert E \rvert)$ procedure that finds shortest paths even in the presence of negative edges, by simply updating all the edges. This avoids the problem that Dijkstra runs into, in which it's possible to update the edges in the wrong order (i.e. negative edge later). The pseudocode of its implementation follows below:

procedure bellman-ford(G,l,s):
Input: same as Dijkstra's, but graph must be directed (otherwise, a single negative edge is already a negative cycle!)
Output: same as Dijkstra's

Algorithm:
for u in V:
	dist[u] = INFTY
	prev[u] = nil
dist[s] = 0

for _ in range(|V| - 1):
	for (u,v) in E:
		if dist[u] < INFTY:
			d[v] = min(d[v], d[u] + l[(u,v)])

Notably, the algorithm above still does not work if there exists a negative cycle! A negative cycle is simply a cycle that allows infinite reduction of the distance. Why doesn't it work? Well, with a negative cycle, the shortest-path problem is ill-posed. There doesn't really exist a shortest path, since, with a negative cycle, the shortest path can have infinitely negative weights.

Note: to check if there exists a negative cycle in the graph, we can also use Bellman-Ford. Simply run the algorithm for one more iteration—if an update to any vertex's distance is observed, there exists a negative cycle, as Bellman-Ford must end within $\lvert V \rvert-1$ iterations if there is a shortest path. After all, a shortest path can traverse through at most $\lvert V \rvert-1$ other nodes before reaching a target node.

Proof of the Bellman-Ford Algorithm:
First, note the correctness of the algorithm for vertices that cannot be reached from the start node, $s$ , as $\mathrm{dist}[v]$ will remain as $\infty$ .

We now aim to show that, after the $i$ th iteration, the Bellman-Ford algorithm correctly finds all shortest paths whose number of edges $\leq i$ . Consider an arbitrary vertex $v$ for which there exists a path from $s$ to $v$ . Let the nodes along the shortest path be denoted $p_{0}=s,p_{1},\dots,p_{k}=v$ . Before the first iteration, $\mathrm{dist}[v]=0$ is known. During the 1st iteration, $(p_{0},p_{1})$ is checked, and the distance to $p_{1}$ is correctly calculated. We can state a similar assertion for the next $k-1$ nodes. Therefore, the shortest path form $s$ to $v$ will certainly be determined after $\lvert V \rvert-1$ iterations. In fact, this proof shows that it is guaranteed for this to be the case, as a shortest path cannot have more than $\lvert V \rvert-1$ edges.

Shortest Path Faster Algorithm (SPFA)

This is an improvement on the Bellman-Ford algorithm. It takes advantage of the idea that not all attempts at relaxation will actually result in a change. SPFA maintains a queue with only relaxed vertices that could further relax their neighbors. So, whenever a neighbor is relaxed, the algorithm puts it on the queue. This, thus, avoids visiting all $n$ vertices every iteration ( $n-1$ iterations).

The worst case of this algorithm is equal to $O(\lvert V \rvert \cdot\lvert E \rvert)$ , like Bellman-Ford. But, in practice, it is more efficient.

Note also that the algorithm can continue forever if there exists a negative cycle; thus, it's necessary to keep track of how many times each vertex has been relaxed and stop the algorithm when a vertex is relaxed for the $n$ th time.

##define f first
##define s second
##define PII pair<int, int>
##define MP make_pair

const int INF = int(1e9);
vector<vector<PII>> adj;

bool spfa(int s, vector<int>& d) {
	int n = adj.size();
	d.assign(n, INF);
	vector<int> cnt(n, 0);
	vector<bool> inq(n, false);
	queue<int> q;
	
	d[s] = 0;
	q.push(s);
	inq[s] = true;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		inq[v] = false;
		
		for (auto edge : adj[v]) {
			int to = edge.f;
			int len = edge.s; // weight
			
			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				if (!inq[to]) {
					q.push(to);
					inq[to] = true;
					if (cnt[to] > n)
						return false; // negative cycle
				}
			}
		}
	}
}

Source

4.7 Shortest Paths in DAGs

Since, in any path of a DAG, the vertices are guaranteed to appear in linearized order, we can simply linearize the DAG first and then visit the vertices in sorted order, relaxing the edges as we go. This algorithm doesn't even require the edges to be positive, either. We can also find the longest paths in a DAG by the same algorithm, just by negating all edge lengths.

procedure dag-shortest-paths(G,l,s)

Input:
- G=(V,E) : DAG
- l = set of edge weights
- s = starting vertex
Output:
- Same as Dijkstra's
  
Algorithm:
for u in V:
	dist[i] = INFTY
	prev[u] = nil
	
dist[s] = 0
toposort(G)
for u in V, linearized:
	for e in E:
		relax(e)