Description
1. (20 pts) Answer True or False to each of the questions below, and explain briefly why you think
the answer is correct..
(a) In the Bellman-Ford algorithm, the maximum number of times that the distance label of a
given node i can be reduced is less than or equal to n − 1, where n is the number of nodes in
the graph.
(b) Bellman-Ford algorithm can be used for finding the longest path in a graph.
(c) In Floyd’s algorithm for finding all-pairs shortest paths, after each major outer loop k, upper
bounds are computed on shortest distances D(i, j) between each pair of nodes i, j. These
upper bounds correspond to the shortest distance among all paths between nodes i and j
which use only intermediate nodes in {1, . . . , k}.
(d) Consider a directed, weighted graph where every arc in the graph has weight 100. For this
graph, executing Dijkstra’s algorithm to find a shortest path tree starting from a given node
is equivalent to performing breadth first search.
(e) Consider a directed, capacitated graph, with origin node O and destination node D. The
maximum flow which can be sent from O to D is equal to the minimum of the following two
quantities: the sum of the capacities of the arcs leaving O, and the sum of the capacities of
the arcs entering D.
(f) In Dijkstra’s algorithm, the temporary distance labels D assigned to nodes which have not yet
been scanned can be interpreted as the minimum distance among all paths with intermediate
nodes restricted to the nodes already scanned.
(g) The worst case complexity of the fastest minimum spanning tree algorithm is O(Nlog(N)),
where N is the number of nodes in the graph.
(h) Consider an undirected graph where, for every pair of nodes i, j, there exists a unique simple
path between them. This graph must be a tree.
(i) Consider a minimum spanning tree T in a connected undirected graph (N, A) which has no
two arcs with equal weights. Then, an arc i,j in T must be either the minimum weight arc
connected to node i or the minimum weight arc connected to node j.
(j) The following three algorithms are examples of greedy algorithms: Dijkstra’s shortest path
algorithm, Kruskal’s minimum spanning tree algorithm, Prim’s minimum spanning tree algorithm.
1
1
2
3
4
5
6
7
9
1
9
5
3
10
4 8
3
6 7
2
11
15
Figure 1:
2. (15 pts) Consider the undirected weighted graph in Figure 1. Show the distance estimates computed
by each step of the Bellman-Ford algorithm for finding a shortest path tree in the graph, starting
from node 1 to all other nodes. For each cycle in the outer that adds an arc record in a
table new distance d(j) and the predecessor p(j) at each node.
2
1
2
3
4
5
6
7
8
9
10
11
1
2
3
13
8
30
25
2
11
17 8
6
7
4
9
5 14
12
15
Figure 2:
3. (15 pts) Consider the weighted, undirected graph in Figure 2. Assume that the arcs can be traveled
in both directions. Illustrate the steps of Dijkstra’s algorithm for finding a shortest paths from node
1 to all others.
3
Figure 3:
4. (15 pts) Consider the graph in Figure 3. This is a directed graph. Use the Floyd-Warshall algorithm
to find the shortest distance for all pairs of nodes. Show your work as a sequence of 4 by 4 tables.
4
