(1) Show d and ⇡ values after each of the |V | 1 passes.
(2) Modify the graph so that it contains at least one negative cycle. Run the Bellman-Ford algorithm again to show how the negative cycle can be detected by the algorithm.
Figure 1: Graph for Question 3.
4. (100points)ThisquestionasksyoutodesignandimplementaGoogle Map-like program using the learned shortest path algorithms.
The map: the map is a non-directed graph G = (V, E). Each vertex v 2 V represents a trac intersection and an edge (u, v) 2 E represents the two-way street (or road) from interactions u to v. The weight on every edge (u,v), denoted with ⌧(u,v), is the time to travel between u and v. You may think of the map looks like Figure 2 (and perhaps much larger).
Figure 2: Illustration map for Question 4. 2
The problem: Without doubt, shortest path algorithms can be used to find a “static” shortest path from starting position s to destination t. But your Google Map-like algorithm should be able to take real- time trac information into consideration and to dynamically choose a shortest path from the current position p to the destination t. That is, at the current position p, the algorithm checks if a travel time change on the street (u, v) and makes an adjustment to the current path.
Requirement 1 (25 points): Describe (in English + mathematical languages) your algorithm that can make an adjustment to the shortest path p t when the travel time on street (u, v) increases from ⌧ (u, v) to ⌧0(u,v), i.e., ⌧(u,v) < ⌧0(u,v). Here (u,v) is assumed to be on the path p t. You need to assess the time complexity for the adjustment step.
Requirement 2 (25 points): Extended from Requirement 1, now (u, v) may not be on the current path p t and travel time (u, v) may also decrease, i.e., it is also possible ⌧(u,v) > ⌧0(u,v). Your algorithm should consider this situation in adjusting the shortest path p t. You need to assess the time complexity for the adjustment step.
** You should write algorithms for requirements 1 and 2 separately.
Requirement 3 (50 points): Implement your algorithm in a pro- gramming language. The input to the program should be a map as described, including a starting position s and a destination position t. The program should accomplish the following tasks.
It consists of a loop such that at each iteration of the loop (which can be control manually or by a system timer), (1) the vehicle moves from interaction p to the next interaction q on the identified shortest path p t, (2) at position q, it checks for travel time changes on streets, and (3) adjust path q t based on the time changes.
The time change information can be available by calling a subroutine that randomly identifies one or more streets (u,v) on the map and randomly changes the travel time of these streets. The loop repeats until the vehicle arrives at the destination t. The program should output the shortest path at every iteration together with the relevant travel time change information.
More realistic situations to consider but not required: While the above situation assumes that travel time changes on streets are synchronized with the time the vehicle arrives at an intersection, in
3
reality, the algorithm should checks periodically trac situations while on the street as well as well just at intersections. We may assume the period to be some time unit and travel time is measured with such unit. So the subroutine used to issue travel time change should also be synchronized with the time period. For example, if the travel time from interaction p to intersection q is ⌧(p,q) = 10 units, the program should check trac and adjust path 10 times on the street (p, q). To deal with these situations, an iteration of the loop in your program should correspond to one time unit.
4