Description
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 immediatelyfollowed 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 w0 corresponds to the same color sequence; i.e., c(w) = c(w0). 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
