Introduction to Algorithms/Shortest Paths 2

Video Link

Shortest Paths 1

Bellman-Ford alg

• computes shortest-path weights $\delta(s,v)$ from source vertex $s\in V$ to all vertices $v\in V$ or reports a negative-weight cycle exists .

Bellman-Ford(G,w,s):
  d[s]<-0
  for each v in V-{s}
    do d[v]<-INF
  for i<-1 to |V|-1
    for each edge (u,v) in E
      do if d[v]>d[u]+w(u,v)
	 then d[v]<-d[u]+w(u,v)
  for each edge (u,v) in E
    do if d[v]>d[u]+w(u,v)
       then report negative-weight cycle

Time is $\Theta(VE)$.

Correctness: if $G=(V,E)$ has no neg-weight cycles, then Bellman-Ford terminates with $d[v]=\delta(s,v)$ for alll $v\in V$.

Proof: Consider $v\in V$.By monotonicity of the $d$ values and Correctness 1, we only need to show at some point $d[v]=\delta(s,v)$.

Let $p=v_{0}=s\to v_{1} \to \dots \to v_{k}=v$ be a shortest path from $s$ to $v$ with minimum number of edges $\implies$ $p$ is a simple path. $\delta (s,v_{i})=\delta (s,v_{i-1})+w(v_{i-1},v_{i})$ by opt. substructure.

$d[v_{0}]=0=\delta (s,v_{0})$. Assume by induction that $d[v_{j}]=\delta(s,v_{j})$ after $j$ rounds for $j<i$.After $i-1$ rounds, $d[v_{i-1}]=\delta (s,v_{i-1})$.During the $i$th round, we relax $(v_{i-1},v_{i})$. Correctness Lemma $\implies$ $d[v_{i}]=\delta(s,v_{i})$.

After $k$ rounds, $d[v]=\delta(s,v),k\leqslant

V

-1$ because $p$ is simple.

Corollary: If Bellman-Ford fails to converge after $

v

-1$ rounds, then must be a neg-weight cycle.

Linear programming

given $m\times n$ matrix $A$, $m$-vector $b$, $n$-vector $c$, find $n$-vector $x$ that maximizes $c^{T}\cdot x$ subject to $Ax \leqslant b$ or determine no such $x$.

Many efficient algs to solve LPs

• simplex <- expon in worst-case but practical.
• ellipsoid <- poly time.
• inner-point <- poly time and practical.
• random sampling

Linear feasibility problem: no objective $c$, find $x$ s.t. $Ax\leqslant b$. Actually no easier than LPs.

Difference constraints

A linear feasibility problem where each row of the matirx $A$ has one 1 and one -1, rest 0’s. Each constraints is of form

\[x_{j}-x_{i}\leqslant w_{ij}\]

Constraint graph: $x_{j}-x_{i}\leqslant w_{ij} \implies$ an edge from $v_{i}$ to $v_{j}$ with $w_{ij}$. $

V

=n,

E

=m$.

Theorem. If constraint graph has negative-weight cycle, then difference constraints are unsatisfiable.

Proof: Let $v_{1} \to v_{2} \to \dots \to v_{k} \to v_{1}$ is a neg-weight cycle. Adding all the constraints leads to contradictory.

Theorem. if no neg-weights cycle in the constraint graph, then different constraints are satisfied.

Proof: Add to $G$ a new vertex $S$ with a weight-0 edge from $s$ to all vertices. Modified graph has no negative weight cycles and has paths from $s$ to every vertex $\implies$ shortest paths exists.

Assign $x_{i}=\delta (s,v_{i})$. Then

\[\delta (s,v_{j})-\delta (s,v_{i})\leqslant w(v_{i},v_{j})\]

Run bellman-ford alg and done.

Corollary: Bellman-Ford solves a system of $m$ difference on $n$ variables in $O(mn)$ time.

Bellman also maximizes $x_{1}+x_{2}+\dots x_{n}$, s.t. $x_{i}\leqslant 0, x_{j}-x_{i}\leqslant w_{ij}$.Also minimizes $\max_{i} x_{i}-\min_{i} x_{i}$.

VLSI-layout

Divide-and-Conquer Algorithm

Problem: place IC features without putting any two features too close to together, e.g. $x_{2}-x_{1}\geqslant d+\epsilon$.

Bellman-Ford solves these constraints and minimizes $\max_{i} x_{i}-\min_{i} x_{i}\implies$ maximizes compactness.