91Ó°ÊÓ

Just like the previous problem, but this time with the Bellman-Ford algorithm.

Here's a proposal for how to find the length of the shortest cycle in an undirected graph with unit edge lengths. When a back edge, say $\left(v,w\right)$, is encountered during a depth-first search, it forms a cycle with the tree edges from $\mathit{w}\mathbf{}\mathit{t}\mathit{o}\mathbf{}\mathit{v}$. The length of the cycle$\mathbf{level}\left[v\right]\mathbf{-}\mathbf{level}\left[w+1\right]$ is where the level of a vertex is its distance in the DFS tree from the root vertex. This suggests the following algorithm:

• Do a depth-first search, keeping track of the level of each vertex.

• Each time a back edge is encountered, compute the cycle length and save it if it is smaller than the shortest one previously seen. Show that this strategy does not always work by providing a counterexample as well as a brief (one or two sentence) explanation.

Question: Often there are multiple shortest paths between two nodes of a graph. Give a linear-time algorithm for the following task.

Input: Undirected graph G = (V , E )with unit edge lengths; nodes$\mathbf{u}\mathbf{,}\mathbf{v}\mathbf{∈}\mathbf{V}$

Output: The number of distinct shortest paths from utov.

Question: Prove that for the array prev computed by Dijkstra's algorithm, the edges $\left\{u,\mathrm{prep}\left[u\right]\right\}\left(\mathrm{forall}∈v\right)$form a tree.

You are given a directed graph $\mathbf{G}\left(V,E\right)$with (possibly negative) weighted edges, along with a specific node $\mathbf{s}\mathbf{∈}\mathbf{V}$and a tree $\mathbf{T}\mathbf{=}\left(V,E\text{'}\right)\mathbf{,}\mathbf{E}\mathbf{\text{'}}\underline{\mathbf{⊂}}\mathbf{E}$. Give an algorithm that checks whether T is a shortest-path tree for G with starting point s . Your algorithm should run in linear time.