Quiz 08
Practice problems for topics on Quiz 08.
Tags in this problem set:
Problem #298
Tags: lecture-14, shortest paths
True or False: It is possible for two arbitrary nodes to have a negative shortest path distance between them without the presence of a negative cycle in the graph.
Solution
True. For example, if there is a single edge \((u, v)\) with weight \(-1\) and no other edges, the shortest path distance from \(u\) to \(v\) is \(-1\), and there is no cycle at all.
Problem #299
Tags: bellman-ford, lecture-14
Suppose the Bellman-Ford algorithm is run on a graph \(G\) that does not contain negative cycles. Let \(u\) be an arbitrary node in the graph, and assume that \(u\) is reachable from the source.
True or False: \(u\)'s estimated distance can change multiple times during the algorithm's execution.
Solution
True.
Suppose there are edges \((s, u)\) with weight 10, \((s, a)\) with weight 1, and \((a, u)\) with weight 1. If \((s, u)\) is updated first, \(u\)'s estimate drops from \(\infty\) to 10. It drops again to 2 once \((s, a)\) and then \((a, u)\) are updated.
Problem #300
Tags: bellman-ford, lecture-14
Recall that Bellman-Ford with early stopping updates edges iteratively until no estimated distances change, at which point the algorithm terminates early. True or False: the number of iterations needed before early termination may depend on the order in which the edges are updated.
Solution
True.
Consider the path graph \(s \to a \to b \to c\). If the edges are updated in order along the path, every distance is correct after one iteration, and the second iteration changes nothing. If they are updated in reverse order, each iteration only fixes one more node, so it takes all three iterations. (With \(|V| = 4\), the outer loop runs at most \(|V| - 1 = 3\) times.)
Problem #301
Tags: bellman-ford, lecture-14
Suppose you have a directed graph with 8 nodes and 7 edges. If you were to run the Bellman Ford Algorithm on this graph with early stopping implemented, what is the minimum number of times the outer for loop could possibly run? You should assume that all 8 nodes are reachable from the source node.
Solution
Answer: 2. In the best situation, the edges would be updated in just the right order so that all of the correct shortest paths are found on the first iteration. On the second iteration, B-F will detect that nothing changed, and it will terminate.
Problem #302
Tags: bellman-ford, lecture-14
Recall that the outer loop of the Bellman-Ford algorithm without early stopping loops for a fixed number of iterations, while the inner loop iterates over each edge of the graph.
Suppose Bellman-Ford with early stopping is run on the graph below using node \(s\) as the source:
What is the fewest number of iterations of the outer loop that can possibly be performed?
Solution
2
Problem #303
Tags: bellman-ford, lecture-14
Suppose Bellman-Ford with early stopping is run on the weighted graph below whose edge weights are unknown to us (but known to the algorithm). The algorithm uses node \(a\) as the source node.
How many iterations of the outer loop will be run in the worst case? Your answer should be a number.
Solution
4
Problem #304
Tags: bellman-ford, lecture-14
Suppose the Bellman-Ford algorithm with early stopping is run on the weighted graph shown below using node \(s\) as the source (the edge weights are intentionally not shown). In the worst case, how many iterations of Bellman-Ford will be performed? That is, how many iterations of the outer for-loop will occur?
Solution
7
Problem #305
Tags: bellman-ford, lecture-14
Consider a ``2-chain'' graph: a graph with \(n\) nodes that is constructed by taking \(n\) nodes labeled 1, 2, \(\ldots\), \(n\), and, for each node \(u\), making an edge to nodes \(u + 1\) and \(u + 2\)(if they are in the graph).
Suppose the Bellman-Ford algorithm without early stopping is run on a 2-chain graph with \(n\) nodes, using node 1 as the source. What is the time taken as a function of \(n\)? State your answer using asymptotic notation.
Solution
\(\Theta(n^2)\)
Problem #306
Tags: bellman-ford, lecture-14
Suppose the Bellman-Ford algorithm is run on the following graph using node \(a\) as the source node:
Suppose when graph.edges is called, the edges are returned in the order:
\((a, b), (c, e), (d, f), (c, d), (b, d), (b, e), (a, c), (e, f) \).
After one iteration of the outer loop of Bellman-Ford, what is the estimated distance to node \(d\)?
Solution
9
Problem #307
Tags: bellman-ford, lecture-14
Recall that the Bellman-Ford algorithm keeps track of the estimated shortest path distance from the source to each node in the graph. These estimates are updated, and eventually become correct, provided that the graph has no negative cycles.
Suppose the Bellman-Ford algorithm is run on the graph below using node \(s\) as the source.
After 2 iterations of the outer loop, which of the nodes listed below are guaranteed to have correct estimated shortest path distances (no matter the order in which graph.edges produces the graph's edges)? Select all that apply.
Solution
\(u_3\), \(u_4\), and \(u_5\) are guaranteed to have correct estimated shortest path distances after 2 iterations of the outer loop. \(s\)'s estimated distance is correct from the start, since it is initialized to \(0\).
Problem #308
Tags: bellman-ford, lecture-14
Suppose Bellman-Ford with early stopping is run on the weighted graph below. The algorithm uses node \(a\) as the source node.
After the third iteration, name all nodes whose shortest path from \(a\) are guaranteed to be estimated correctly.
Solution
1st option: \(\{a,b,c,e,f\}\)
Problem #309
Tags: lecture-14, breadth first search
Suppose that every edge in the weighted graph \(G\) has weight -5. True or False: breadth first search on this graph will compute a longest path from the source to every node in the graph (that is, a path with greatest possible total edge weight).
You may assume that every node in the graph is reachable from the source.
Solution
True.
A path with \(k\) edges has total weight \(-5k\), so the path with the greatest total weight is the one with the fewest edges. BFS finds exactly this path: the path with the fewest edges from the source to each node.
Problem #310
Tags: bellman-ford, lecture-14
Consider running Bellman-Ford on the graph below using node \(u\) as the source.
Part 1)
Suppose that graph.edges produces edges in the following order:
After two iterations of the outer for-loop, what is the estimated shortest path distance for node \(b\)?
Solution
7.
After iteration 1, the estimates are \(a = 2\), \(c = 7\), \(d = 9\), \(e = 13\)(\(b\) is still \(\infty\)). In iteration 2, \(b\) becomes \(16\) via \((a, b)\), \(d\) becomes \(5\), then \(b\) becomes \(13 - 6 = 7\) via \((e, b)\), and \(e\) becomes \(9\). So after two iterations, the estimate for \(b\) is 7.
Part 2)
With the same edge order as in the previous part, how many iterations does the outer for-loop take? The algorithm includes early stopping.
Solution
4.
Continuing from the previous part: in iteration 3, \(b\) becomes \(9 - 6 = 3\). Iteration 4 changes nothing, so the algorithm stops after 4 iterations.
Part 3)
Now suppose that graph.edges produces edges in a different order:
How many iterations does the outer for-loop take? The algorithm includes early stopping.
Solution
3.
Iteration 1 only sets \(a = 2\) and \(c = 7\), since the edges out of \(u\) come last. In iteration 2, \(b = 16\), \(d = 5\), \(e = 24\) then \(9\), and \(b = 3\). Iteration 3 changes nothing, so the algorithm stops after 3 iterations.