Due Friday, October 21, in Gradescope.
Suppose that you are trying to drive home for the winter holidays, and you have a choice of several routes, but some of them might be closed because of snow. Suppose also that you have already translated this problem into finding a path from a start vertex to a destination vertex in a directed acyclic graph, where each edge represents a road on a possible route, directed in the direction that you would take it. For each edge, you know the probability that it is snow-free. The probability that an entire route is snow-free can be calculated by multiplying the probabilities for each of its edges (we make the unrealistic assumption that snow closures are independent of each other). Describe an efficient algorithm for finding the route with the greatest probability of staying snow-free.
(Your answer can be pseudocode, a short description of the algorithm, or a description of how to modify the input so that one of the algorithms described in this week's lectures can solve this problem. For full credit the worst-case runtime of your algorithm should be as fast as possible.)
The following algorithm for single-source shortest paths, starting from a vertex \(s\) in a directed graph, will work on directed acyclic graphs, but for other graphs it will sometimes return incorrect answers.
163 students only: A given directed graph may have more than one depth-first spanning tree, depending on the order in which the search loops through the neighbors of each vertex. For instance, the graph with four vertices \(\{s,x,y,z\}\) and six edges \(s\to x\), \(s\to y\), \(x\to y\), \(x\to z\), \(y\to x\), and \(y\to z\) has two depth-first search trees, \(s\to x\to y\to z\) and \(s\to y\to x\to z\). Choose positive lengths for the six edges of this graph, so that the algorithm above will compute the correct distance from \(s\) to \(z\) for a depth-first search that produces the first tree, and will compute an incorrect distance for a depth-first search that produces the second tree. Include in your answer the two distances that it computes.
265 students only: Describe a method for testing in linear time whether the \(D\) and \(P\) values constructed by this algorithm are correct, or whether at least one is incorrect.
(If some values are incorrect, just report that fact; you do not need to determine the exact set of incorrect values. Hint: use relaxation again.)
163 students only: Will the Bellman–Ford algorithm compute correct shortest path distances on an undirected graph that has no cycles (that is, an undirected forest) when some edge lengths are negative? Explain why or why not.
265 students only: Will the algorithm from question 2 always compute correct shortest path distances on this kind of graph? Explain why or why not.
Let \(G\) be a directed graph consisting of four vertices \(\{a,b,c,d\}\) connected in a cycle, with the four edge lengths \(\ell(a\to b)=1\), \(\ell(b\to c)=-2\), \(\ell(c\to d)=5\), and \(\ell(d\to a)=-3\). What are the modified lengths for these edges computed by Johnson's algorithm?