Zhancun Mu

I am a student at PKU and here is my blog.

2 minute read

VIdeo Link

Paths

  • consider digraph $G=(V,E)$ with edge weights given by function $w: E\to \mathbb R$.
  • path $p=v_{1}\to v_{2} \to \dots \to v_{k}$ has weight $w(p)=\sum_{i=1}^{k-1}w(v_{i},v_{i+1})$.

Shortest path from $u$ to $v$ is a path of minimum weight from $u$ to $v$.

Shortest-path weight from $u$ to $v$ is

\[\delta (u,v)=\min \\{ w(p):p \text{ path from }u \text{ to }v\\}\]

and $\infty$ if no path.

Negative edge weights $\implies$ some shortest paths may not exist.

Opt. substructure: a subpath of ashortest path is a shortest path.

Proof: Cut and paste.

Triangle inequality: For all vertices $u,v,x \in V$, $\delta (u,v)\leqslant \delta (u,x)+\delta (x,v)$.

Single-source shortest paths problem

from given source vertext $s\in V$, find shortest-path weights $\delta(s,v),\forall v\in V$.

Today: assumming $w(u,v)\geqslant 0 \implies$ shortest paths exists provided paths exist.

Idea: greedy.

  • maintain set $S$ of vertices whose shortest-path distance from $s$ is known.
  • at each step add to $S$ the vertex $v\in V-S$ whose distance estimate is minimum.
  • Update distance estimates of vertices that are adjacent to $v$.

Dijkstra’s alg

d[s]<-0
for each v in V-{s}
  do d[v]<-INF
s<-empty
Q<-V // priority queue keyed on d
while Q is not empty
  do u<-Extract-Min(Q)
     S<-S and {u}
     for each v in Adj[u]
       do if d[v]>d[u]+w(u,v)
	  then d[v]=d[u]+w(u,v) //relaxation

Shortest path tree = for each vertex $v$ last edge $(u,v)$ relased.

Correctness:

Correctness 1: Invarient $d[v]\geqslant \delta(s,v)$ for all $v\in V$ holds after initialization & any seq of relaxations.

Proof:

  • After initialization, true.
  • Suppose for contradiction that Invarient is violated. Consider first violation $d[v]<\delta (s,v)$ cause by relaxation $d[v]\leftarrow d[u]+w(u,v) <\delta(s,v)$. But $d[u]+w(u,v)\geqslant \delta(s,u)+w(u,v)\geqslant \delta (s,v)$.

Lemma: Suppose $s \to \dots \to u \to v$ is a shortest path. If $d[u]=\delta(s,u)$ and relax edge $(u,v)$ then $d[v]=\delta(s,u)$ after relaxation.

Proof:

\[\delta(s,v)=w(s\to \dots\to u)+w(u,v)=\delta(s,u)+w(u,v)\]

Correctness 1: $d[v]\geqslant \delta(s,v)$. Either $d[v]=\delta(s,v)$ before relaxation $\implies$done, or $d[v]>\delta(s,v)$ before relaxation $\implies$ we relax and $d[v]=\delta(s,v)$.

Correctness 2: when Dijkstra terminates $d[v]=\delta(s,v),\forall v\in V$.

Proof: $d[v]$ doesn’t change when added to $S\implies$ show $d[v]=\delta(s,v)$ when $v$ is added to $S$.

Suppose for contradiction that $u$ is the first vertex (about to be) added to $S$ for which $d[u] \neq \delta(s,u) \implies d[u]>\delta(s,u)$.

Let $p$ be a shortest path from $s$ to $u\implies w(p)=\delta(s,u)$. Consider first edge $(x,y)$ where $p$ exists $S$. First violation $\implies d[x]=\delta(s,x)$. When we added $x$ to $S$, we relaxed $(x,y)$, so by lemma $d[y]=\delta(s,y)\leqslant \delta(s,u)<d[u]$. But $d[y]\geqslant d[u]$ (Extract-Min).

Time: $ V T_{extract}+ E T_{decrease}$.

Unweighted graphs

\[w(u,v)=1,\forall u,v \in V\]

BFS using FIFO queue. Relaxation is:

  • if $d[v]=\infty$, $d[v]=d[u]+1$, Inqueue(Q,v).

Time is $\Theta(V+E)$.

Comments

You May Also Enjoy