Cpt S 350 Homework #8
Please print your name!
Let G be a directed graph with each edge assigned with a positive number
called its weight. In particular, there is a designated node in G called the
initial node and there is a designated node in G called the final node. Additionally, each edge is also decorated with a color in Σ = {red, yellow, green}.
Try to sketch ideas in designing efficient algorithms for the following problems.
1. For a given number k, enumerating the first i-th shortest paths, for all
1 ≤ i ≤ k, from the initial to the final.
2. Finding a shortest path that does not have a red edge immediately
followed by a yellow edge.
3. For each path w from the initial to the final, one can collect the colors
on the path and therefore, a color sequence c(w) is obtained. Notice that, it
might be the case that two distinct paths w and w
0
corresponds to the same
color sequence; i.e., c(w) = c(w
0
). Computing the size of the set {c(w) : w is
a path from the initial to the final}.
4. For each path w from the initial to the final, one can multiply the
weights on the path and therefore, a number W(w) is obtained. Find a path
w from the initial to the final such that W(w) is minimal.
1
