Description
Question 1. Let G1 be a directed weighted graph with 5 vertices A, B, C, D, E. This graph
G1 and its associated weight function w1 are depicted in Figure 1, where the values next to the
edges represent the corresponding weights.
(i) Run the Bellman–Ford algorithm on graph G1, with weight function w1 and source vertex
A, using the relaxation order (A, B),(A, C),(B, C),(B, E),(B, D),(E, D),(D, C),(D, B).
Please give the table of d and π values for all vertices, obtained at the end of each pass of all
edges of G1 in the given relaxation order. The rows of your table should correspond to the
iterations of the algorithm. You should include all iterations, including the initialization
and the final check. You may write each entry of your table in the form of vertex(d, π).
[2 points]
(ii) Next, consider a new weight function w
0
1
on the same graph G1, where w
0
1
(B, D) = −3,
and where w
0
1
(e) = w1(e) for all other edges e 6= (B, D) in G1. Run the Bellman–Ford
algorithm on graph G1, with weight function w
0
1
and source vertex A, using the same
relaxation order as before. Please give the new table of d and π values for all vertices,
obtained at the end of each pass of all edges of G1 in the given relaxation order. Again,
you should include all iterations in your table, including the initialization and the final
check. [3 points]
Figure 1: A directed weighted graph G1 for use in Question 1.
Question 2. Design an algorithm that satisfies the following conditions:
(i) The algorithm takes as its inputs a directed weighted graph G, its associated weight
function w, and a vertex s of G.
(ii) The algorithm returns the adjacency matrix of a shortest-paths tree (for G) rooted at s, if
G has no negative-weight cycles reachable from s, and returns the character string ‘error’
otherwise.
[Hint: Modify the Bellman–Ford algorithm.] [5 points]
1
For the next two questions, consider a directed weighted graph G2 with 5 vertices s, t, x, y, z.
This graph G2 and its associated weight function w2 are depicted in Figure 2, where the values
next to the edges represent the corresponding weights.
Figure 2: A directed weighted graph G2 for use in Questions 3 and 4.
Question 3. Run Dijkstra’s algorithm on graph G2, with weight function w2 and source vertex
x. In a table format, please give the d and π values of all vertices, as well as the set S and
the priority queue Q, obtained at the end of each iteration of the while loop in Dijkstra’s
algorithm. You may assume that Q is implemented using a min-heap, and you may write Q
in its array representation. The first row of your table should correspond to the initialization.
Each subsequent row of your table should correspond to an iteration of the while loop. Also,
please draw the final shortest-paths tree for G2 as computed by Dijkstra’s algorithm. [5 points]
Question 4. Run Dijkstra’s algorithm on graph G2, with weight function w2 and source vertex
t. Similar to tbe previous question, please give in table format the d and π values of all vertices,
as well as the set S and the priority queue Q, obtained at the end of each iteration of the while
loop in Dijkstra’s algorithm. You may assume that Q is implemented using a min-heap, and
you may write Q in its array representation. The first row of your table should correspond to
the initialization. Each subsequent row of your table should correspond to an iteration of the
while loop. Also, please draw the final shortest-paths tree for G2 as computed by Dijkstra’s
algorithm. [5 points]
As discussed in class, when running Dijkstra’s algorithm on a directed weighted graph, we
assume that the weights of all edges are all non-negative. In the next question, we shall take a
closer look at an example to understand what happens when the weights of the edges are not
all non-negative.
Question 5. Let G3 be a directed weighted graph with 4 vertices s, x, y, z, and with associated
weight function w3. Suppose we run Dijkstra’s algorithm on G3 with weight function w3 and
source vertex s. The initialized graph, together with the weights of all edges, and the d values
of all vertices, are depicted in Figure 3. Values next to the edges represent the corresponding
weights, while values indicated within circles represent the d values of the corresponding vertices.
Please draw all subsequent graphs, together with the weights of all edges, and the d values of all
2
vertices, that correspond to the end of each iteration of the while loop in Dijkstra’s algorithm.
What is the corresponding “shortest-paths tree” for G3, as incorrectly computed by Dijkstra’s
algorithm? What should be a correct shortest-paths tree for G3? In your own words, explain
in detail why Dijkstra’s algorithm has failed to find a shortest path from s to z. [5 points]
s 0
y ∞
∞ x
∞ z
1
2
−3
3
1
Figure 3: A directed weighted graph G3 for use in Question 5.
3