Problem $5(20$ Points$)$

Dynamic Programming

Consider the road network shown in Fig. $1$ where the nodes indicate places, the edges

indicate roads and the numbers at the edges indicate the traveling time between the

nodes conected by the edge. The goal is to travel from node S to node E traversing

the fastest route.

$($a$)$ Solve the fastest route problem for the road network given in Fig. $1$ using dynamic

programming! Mark the fasted route in Fig. $1!$

Figure. $1$: Road network without congestion.

$($b$)$ Now, a congestion changes the traveling time between two nodes as indicated

in Fig. $2.$ Solve the fastest route problem of the road network given in Fig. $2$

using dynamic programming! Which nodes have to be re$-$evaluated given your

calculations in $($a$)?$ Mark the fastest route in Fig. $2!$