## 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 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.