CIS 121—Data Structures and Algorithms—Spring 2020
Dijkstra’s and Minimum Spanning Trees—Monday, March 30 / Tuesday, March 31
Readings
• Lecture Notes Chapter 20: Dijkstra’s Algorithm
• Lecture Notes Chapter 21: Minimum Spanning Trees
Problems Problem 1
1. True or false: Dijkstra’s algorithm will not terminate if run on a graph with negative edge weights.
Solution: False. The algorithm will terminate, but it might return a wrong answer.
2. True or false: If we double the weights of all the edges in a graph, then Dijkstra’s algorithm will
produce the same shortest path.
Solution: True. Any scaling by a positive factor on the weights will not affect the calculation of shortest paths. You can think of it as unit-conversion. For instance, if you converted weights from expression in miles to kilometers, that would not affect the relative ordering of shortest paths.
Problem 2
Does Kruskal’s algorithm work on a graph with negative weights? How about Prim’s?
Solution
Yes. Kruskal’s algorithm will still select the lowest weight edges in order (more negative edges first). Sim- ilarly, since Prim’s is selecting the lowest weight edge that crosses the cut (from the cut property), the algorithm works with negative edge weights.
Interestingly, you can also find the most negatively weighted edge in the graph, and add that weight to every edge in the graph to make all the edge weights non-negative. Think about why adding a constant to all the edge weights broke Dijkstra’s algorithm but not Prim’s, despite their similarities.
Problem 3
Say we have some MST, T, in a positively weighted graph G. Construct a graph G′ where for any weight w(e) for edge e in G, we have weights (w(e))2 in G′. Does T still remain an MST in G′? Prove your answer. Now if G also had negative weights, would your answer change from the previous part? Prove your answer.
Solution
If G only has positive weights, then this claim holds. Proof by contradiction: assume the claim does not hold. Let us say we are using Kruskal’s algorithm (similar argument can be used for Prim’s). Consider the first edge where the algorithms running on G and G′, diverged. Then we must have that the algorithm selected some edge e′ within G′ instead of e within G. Then w(e) < w(e′) but w(e)2 > w(e′)2. Note that this is not possible for positive integers, and thus we have a contradiction. However, this claim is possible for negative integers! Thus, if G had negative weights, our answer would change to no, T is not necessarily an MST in G′.
1
Solution Set
Note that in general, any change to the edge weights that preserves their relative ordering suffices.
Problem 4
Imagine we have a graph G where all edge weights are equal. Design an algorithm to efficiently find an MST of G. Analyze the running time.
Solution
The intuition here is that we can find any spanning tree, and it will be the minimum spanning tree. Thus, our optimal algorithm would be to run DFS and only keep track of the tree edges (so we don’t introduce any cycles). Notice at any step we can choose any edge, since the edge weights are all equal. You can do a similar thing with BFS. The running time is therefore O(|E| + |V |).
Problem 5
Suppose that we have found an MST T of a graph G, but soon after, we are told that an edge not in T has a lower weight than we at first thought, and as such our MST is now invalid. Is it guaranteed that we can fix our tree by removing an edge and adding a different one? If so, explain how. If not, provide a counterexample.
Solution
If we can be sure that our MST is invalid because of this change, it follows that the modified edge e exists in all possible MSTs of the new graph. Let us add e to our MST. This has now created a cycle, and we no longer have a tree. We may fix this by removing a particular edge.
The cycle must have some maximal edge. This is the edge that we would not have encountered in our MST creation in the new graph, as it will be the last of the edges in the cycle to be added. Since we are given that the new edge is necessary, the maximal edge must be distinct from e. Thus we may remove this edge, after which we will again have a valid MST.
2
Solution Set