- There are no forward edges.
- For each tree edge $\u27e8u,v\u27e9$, we have $d[v]=d[u]+1$.
- For each cross edge $\u27e8u,v\u27e9$, we have $d[v]\le d[u]+1$.
- For each back edge $\u27e8u,v\u27e9$, we have $0\le d[v]\le d[u]$.

def bfs(V, adj, s): for each u in V: color[u] = WHITE d[u] = INFINITY p[u] = NIL color[s] = GRAY d[s] = 0 Q = {s} while Q is not empty: u = head of Q for each v in adj[u]: if color[v] == WHITE: color[v] = GRAY d[v] = d[u] + 1 p[v] = u append v to end of Q remove u from head of Q color[u] = BLACK return (d, p)

- Tree Edge - A tree edge is an edge that is in the output tree of some graph search algorithm, such as the breadth first search.
- Forward Edge - An edge not in the output tree that connects a vertex to a descendent in the output tree.
- Back Edge - An edge of the original graph that connects a vertex to its ancestor in the output tree.
- Cross Edge - All other edges. Edges not in the output tree that is neither a forward edge nor a back edge.

- There are no forward edges.
For a forward edge
$\u27e8u,v\u27e9$ to exist,
$\u27e8u,v\u27e9$ must not be in
the BFS tree and
$u$ is an ancestor of
$v$ in the BFS tree. Thus,
$d[u]+1<d[v]$ must hold. That is, there must be at least one
vertex in the predecessor path from
$v$ to
$u$. Otherwise, it would
imply that
$\u27e8u,v\u27e9$ was in the BFS tree and would not be
considered a forward edge.
Figure 2: For a forward edge $\u27e8u,v\u27e9$ to exist, the path from $u$ to $v$ in the BFS tree must contain at least one intermediate node. Thus the following condition must hold $d[u]+1<d[v]$. **Statement 1:**When $u$ is the head of the GRAY queue of discovered vertices, then it is made the ancestor of all adjacent vertices that are WHITE. Each is also made GRAY and added to the end of the queue of discovered vertices. For $\u27e8u,v\u27e9$ to exist in the graph but not be included in the BFS tree, $v$ could not have been WHITE when $u$ was the head of the queue. Which means that $v$ was either BLACK or GRAY.**Statement 2:**If $v$ was BLACK, then $v$ has been visited before $u$. Thus, $d[v]\le d[u]$. So $u$ cannot be an ancestor of $v$.**Statement 3:**If $v$ was GRAY, then $v$ has been discovered before $u$ became the head of the queue. In fact, $v$ is in the queue behind $u$ when $u$ was the head of the queue. Any new vertices discovered while $u$ is the head of the queue will have a distance of $d[u]+1$. But since $v$ was in the queue before any of these newly discovered nodes, $d[v]\le d[u]+1$. Thus, whether $v$ was BLACK or GRAY when $u$ was the head of the queue, none of the conditions allow forward edges to exist. Proving that there are no forward edges in a BFS tree. - For each tree edge $\u27e8u,v\u27e9$, we have $d[v]=d[u]+1$. Following the BFS tree construction, if $\u27e8u,v\u27e9$ is a tree edge, then $d[v]=d[u]+1$, because $u$ is a parent of $v$ in the BFS tree.
- For each cross edge $\u27e8u,v\u27e9$, we have $d[v]\le d[u]+1$. From statement 3, any edge $\u27e8u,v\u27e9$ excluded from the BFS tree must have $d[v]\le d[u]+1$.
- For each back edge $\u27e8u,v\u27e9$, we have $0\le d[v]\le d[u]$. If $\u27e8u,v\u27e9$ is a back edge, then $v$ must be an ancestor of $u$. So $d[v]<d[u]$. Since $v$ may very well be the source $s$, $0\le d[v]$.

$W=\left(\begin{array}{cccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 8\hfill & \hfill \infty \hfill \\ \hfill \infty \hfill & \hfill 0\hfill & \hfill \infty \hfill & \hfill 2\hfill \\ \hfill \infty \hfill & \hfill \infty \hfill & \hfill 0\hfill & \hfill \infty \hfill \\ \hfill \infty \hfill & \hfill \infty \hfill & \hfill 3\hfill & \hfill 0\hfill \end{array}\right)={M}^{(1)}$ |

Multiplying ${M}^{(1)}\times W$ will give us ${M}^{(2)}$. This is the shortest path between any pair of vertices using

${M}^{(2)}=\left(\begin{array}{cccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 8\hfill & \hfill \text{3}\hfill \\ \hfill \infty \hfill & \hfill 0\hfill & \hfill \text{5}\hfill & \hfill 2\hfill \\ \hfill \infty \hfill & \hfill \infty \hfill & \hfill 0\hfill & \hfill \infty \hfill \\ \hfill \infty \hfill & \hfill \infty \hfill & \hfill 3\hfill & \hfill 0\hfill \end{array}\right)$ |

Thus, in order to find all pairs of shortest paths in $G$, we need to find ${M}^{(n-1)}$; because that would give us all pairs shortest paths of $G$ of at most $n-1$ edges. Hence, we calculate: ${M}^{(1)},{M}^{(2)},{M}^{(3)},\dots ,{M}^{(n-1)}$, where ${M}^{(i)}={M}^{(i-1)}\times W$. With repeated squaring, we only need to calculate:

${M}^{(1)},{M}^{(2)},{M}^{(4)},\dots ,{M}^{({2}^{\lceil {\mathrm{log}}_{2}(n-1)\rceil})},$ |

where ${M}^{(2i)}={M}^{(i)}\times {M}^{(i)}$. Each multiplication is $O({n}^{3})$ time. Since the number of multiplication is $O({\mathrm{log}}_{2}n)$, the runtime of repeated squaring is $O({n}^{3}{\mathrm{log}}_{2}n)$. If $D$ is given, then the runtime is $O({n}^{3}{\mathrm{log}}_{2}D)$.

File translated from T

On 4 Apr 2006, 15:41.