(b) Your algorithm UpdateMST(T,G,w0, u, v) needs to be writ-
ten in English + mathematical languages. You will not get
credit if it is written in any programming language.
3. (15 points) Consider algorithmBellman-Ford on the directed graph
in Figure 1, using vertex 4 as the source.
(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. (100 points) This question asks you to design and implement a Google
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 tra�c 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).
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 tra�c 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
2
Figure 2: Illustration map for Question 4.
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
3
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 re-
ality, the algorithm should checks periodically tra�c 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 tra�c 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.
Format of the input graph (small example):
n=5
s=1
t=5
0, 23, 8, 25, 9
23, 0, 15, 7, 10
8, 15, 0, 28, 17
25, 7, 28, 0, 6
9, 10, 17, 6, 0
Desirable output format (small example):
Shortest path from current position 1:
1 –> 3 –> 2 –> 4 –> 5
Distance = 35
Traffic change: (3, 2) = 35
Shortest path from current position 3:
3 –> 4 –> 2 –> 5
Distance = 34
…
4