Shortest paths with turn penalties. Figure 4. 15(b) gives a road network in which all road segments are parallel to either the x-axis or the y-axis, The figure also gives the traversal costs of arcs. Suppose that we incur an additional cost (or penalty) of α units every time we make a left turn. Describe an algorithm for solving the shortest path problem with these turn penalties and apply it to the shortest path example in Figure 4.15(b). Assume that α = 5.
