In this lecture, restricted cases for shortest-paths algorithms are covered including:

• Only non-negative edge weights allowed: Dijkstra’s algorithm
• Input graph is acyclic (DAG): single-source s-p algorithm for DAGs

Dijkstra’s shortest-paths algorithm

We make the critical assumption that all edge weights are non-negative. For convenience, also assume all nodes are reachable from $s$.

Dijkstra's Shortest-paths Algorithm

def dijkstra(G, w, s):
	(V, E) = G
	
	relax_init(G, s) # from relaxation technique
	S = set() # nodes for which we know d[v] = delta(s,v)
	Q = V # other nodes in a Priority Queue with keys d[.]
	
	while not empty(Q):
		u = extract_min(Q) # find u with minimum d[.] value in Q
		S = S | {u}
		
		for node v in Adj[u]:
			relax_edge(u, v, w)

Correctness of Dijkstra’s algorithm

We look at an intermediate state of the computation (at the end of one iteration).

Set $S$ grows by one node per iteration. (1st iter: $\{s\}$, last iter: $V$) All edges from nodes in $S$, and only these edges, have been relax’ed. All nodes in $S$ or at the end of edges from $S$:

• have finite $d[.]$ values (by induction)
• have parents, forming a tree (no negative cycle and property 8)

For all other nodes, $d[.]=\infty$, and not in the parent tree.

At the end of the computation:

Set $S$ is $V$. For each $v\in V$, $d[v]$ is finite and $d[v]\ge \delta (s,v)$. The parent subgraph is a tree (rooted at $s$) which includes all nodes.

We haven't shown yet that the computed tree is a shortest-paths tree and the $d[.]$ values are the shortest-path weights.

The Crucial Property (invariant of Dijkstra’s)

The crucial property (invariant of computation of Dijkstra’s algorithm) is that: at the end of each iteration (on the main loop) of Dijkstra’s algorithm, for each node $v\in S$: $d[v]=\delta (s,v)$.

This property can be shown by induction on the number of iterations. Base Case Property holds on first iteration $S=\{s\},d[s]=0=\delta (s,s)$

Inductive Case Assume the invariant holds at the end of some iteration (not last one): $\text{for each }v\in S,d[v]=\delta (s,v)$

Let $u$ denote the node selected in the next (current) iteration.

Show that the invariant holds at the end of the current iteration (after $u$ has been added to set $S$). That is, show $d[u]=\delta (s,u)$.

In other words, we have to show that at the beginning of the current iteration, $d[u]$ is the shortest-path weight from $s$ to $u$.

We have $d[u]\ge \delta (s,u)$ (relaxation technique).

Let’s show that $d[u]\le \delta (s,u)$.

• Take any (simple) path $R$ from $s$ to $u$ and show its weight $w(R)\ge d[u]$.
• Let $z$ be the first node on path $R$ which is outside $S$, and let $y$ be the predecessor of $z$ on $R$ (so $y\in S$).
• Let $R1$ be the initial part of the path $R$ ending at node $y$, and let $R2$ be the part of the path $R$ from node $z$ to the final node $u$. $\begin{array}{rl}w(R)& =w(R1)+w(y,z)+w(R2)\\ & \ge d[y]+w(y,z)+w(R2)\\ & \ge d[z]+w(R2)\\ & \ge d[u]+w(R2)\\ & \ge d[u]\end{array}$ The inequalities in above follow from: the inductive assumption, RELAX($y,z$) done, the rule for selecting $u$, and the non-negative weights of edges, respectively.

Hence, no path from $s$ to $u$ has smaller weight than $d[u]$, so $d[u]\le \delta (s,u)$.

Running time of Dijkstra’s algorithm

Using an unordered list

Using an ordered list

lgt

Priority Queue using a heap

Shortest-paths algorithms for DAGs

Incomplete