The customer of an advertisement company wants to advertise its products on billboards along a stretch of a heavily traveled highway that runs west to east for
M=20
miles. The customer insists that drivers along the highway see one of these billboards every 5 miles or less. The advertisement company has identified possible billboards that it could rent to satisfy the customer's request. These billboards are located at marker miles
x 1
​
,x 2
​
,…,x n
​
(from the west end of the highway), and are such that
x 1
​
​
<… ​
. The renting cost of the billboard located at marker mile
x i
​
is
c i
​
>0
thousands dollars for the duration of the advertisement campaign. The headquarters of the customer are located at marker mile 0 where a large billboard is already present. The advertisement company must select billboard locations so as to minimize the total renting costs. The locations
x i
​
and renting costs
c i
​
of the billboards are given in the following table. Questions: 1. Formulate this problem as a shortest-path problem. In particular, you should draw the vertices and arcs of the network. You should also clearly indicate the cost of each arc, together with the source and the sink of the shortest path. 2. Use Dijkstra's algorithm to solve this shortest path problem. Draw the network and its associated labels after each iteration. Describe the optimal solution to the shortest path problem, and also describe what billboards the advertisement company must rent.