Nondeterministic Iteration: Examples
Shortest Path from a Source
We are given a matrix \(W\) of numbers which represents a directed
graph where \(W[i,j]\) is the weight of the edge
\((i,j)\). If edge \((i, j)\) does not exist then \(W[i,j]\) is a
suitably large value \(inf\). Edge weights may be negative. There are no
cycles of negative length in
the graph. The problem is to find the shortest path from vertex
\(0\) to all the other vertices.
Let \(d\) be an array where \(d[i]\) becomes the weight of the
shortest-weight path to \(i\).
Nondeterministic Iteration
Initially
\(
d[0] = 0
\)
For \(i \neq 0\): \(d[i] = inf\)
Iteration
For all \(i, j\):
\(
d[j] > d[i] + W[i,j] \quad \rightarrow \quad d[j] = d[i] + W[i,j]
\)
Sorting
Sort a vector \(V\) of numbers, in place, in increasing order. Let \(N\) be the length of
\(V\).
Let \(V^{(0)}\) be the initial value of \(V\).
Nondeterministic Iteration
Initially
\(
V = V^{(0)}
\)
Iteration
Flip
any out-of-order adjacent pair.
For all \(i\) where \(0 < i < N\):
\(
V[i-1] > V[i] \quad \rightarrow \quad V[i-1], V[i] = V[i], V[i-1]
\)
K. Mani Chandy,
Emeritus Simon Ramo Professor,
California Institute of Technology