$w(p)=\sum _{i=1}^{k}w({v}_{i-1},{v}_{i}).$ |

The weight of a shortest path from $u$ to $v$ is defined by $\delta (u,v)=min\{w(p):$ $p$ is a path from $u$ to $v\}$.

INITIALIZE $(G,s)$

1 $d[s]$$\leftarrow $$0$

2 $p[s]$$\leftarrow $NIL

3forall $v\in V-\{s\}$

4do$d[v]$$\leftarrow $$\infty $

5 $p[v]$$\leftarrow $NIL

RELAX $(u,v,w)$

1if$d[v]>d[u]+w(u,v)$

2then$d[v]$$\leftarrow $$d[u]+w(u,v)$

3 $p[v]$$\leftarrow $$u$

DIJKSTRA-SHORT $(G,w,s)$

1 INITIALIZE $(G,s)$

2 $S$$\leftarrow $$\varnothing $

3 $Q$$\leftarrow $$V$

4while$Q\ne \varnothing $

5do$u$$\leftarrow $EXTRACT-MIN $(Q)$

6 $S$$\leftarrow $$S\cup \{u\}$

7foreach vertex $v\in \text{Adj}[u]$

8doRELAX $(u,v,w)$

BELLMAN-FORD $(G,w,s)$

1 INITIALIZE $(G,s)$

2for$i$$\leftarrow $$1$to$|V|-1$

3doforeach edge $(u,v)\in E$

4doRELAX $(u,v,w)$

5foreach edge $(u,v)\in E$

6doif$d[v]>d[u]+w(u,v)$

7thenreturnFALSE

8returnTRUE

DAG-SHORTEST $(G,w,s)$Figure 5 shows an example execution of DAG-SHORTEST on a DAG.

1 Topologically sort the vertices of $G$

2 INITIALIZE $(G,s)$

3foreach vertex $u$ taken in topologically sorted (increasing) order

4dofor$v\in \text{Adj}[u]$

5doRELAX $(u,v,w)$

- Simplex algorithm
- Ellipsoid algorithm
- Karmarkkar's algorithm

$x}_{j}-{x}_{i}\le {b}_{k$ |

where $1\le i,j\le n$ and $1\le k\le m$. For example, a set of four unknowns $\{{x}_{1},{x}_{2},{x}_{3},{x}_{4}\}$, and 6

$\begin{array}{ccc}\multicolumn{1}{c}{{x}_{1}-{x}_{2}}& \le \hfill & 6\hfill \\ \multicolumn{1}{c}{{x}_{1}-{x}_{3}}& \le \hfill & -4\hfill \\ \multicolumn{1}{c}{{x}_{2}-{x}_{3}}& \le \hfill & -10\hfill \\ \multicolumn{1}{c}{{x}_{3}-{x}_{4}}& \le \hfill & 14\hfill \\ \multicolumn{1}{c}{{x}_{4}-{x}_{2}}& \le \hfill & -4\hfill \\ \multicolumn{1}{c}{{x}_{4}-{x}_{1}}& \le \hfill & -10\hfill \end{array}$ |

... can be represented as ...

$\left(\begin{array}{cccc}\hfill 1\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right)\left(\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \\ \hfill {x}_{4}\hfill \end{array}\right)\le \left(\begin{array}{c}\hfill 6\hfill \\ \hfill -4\hfill \\ \hfill -10\hfill \\ \hfill 14\hfill \\ \hfill -4\hfill \\ \hfill -10\hfill \end{array}\right)$ |

Given a system $\mathrm{Ax}\le b$ of difference constraints, the corresponding

$V=\{{v}_{0},{v}_{1},{v}_{2},\dots ,{v}_{n}\}$ |

... where $n$ is the number of unknowns, ${v}_{0}$ is a special source vertex created, and ${v}_{i}$ corresponds to ${x}_{i}$ for $1\le i\le n$. Also, the set of edges ...

$E=\{\u27e8{v}_{i},{v}_{j}\u27e9:{x}_{j}-{x}_{i}\le {b}_{k}\hspace{0.5em}\mathrm{is}\hspace{0.5em}a\hspace{1em}\mathrm{constraint}\}\cup \{\u27e8{v}_{0},{v}_{i}\u27e9:i=1,\dots ,n\}$ |

$x=\{\delta ({v}_{0},{v}_{1}),\delta ({v}_{0},{v}_{1}),\dots ,\delta ({v}_{0},{v}_{n})\}$ |

is a feasible solution for the system. Figure 6 shows how this is done for the example with four unknowns above.

File translated from T

On 31 Mar 2006, 18:12.