Problem : Show that in a weighted, directed graph with possibly negative weight edges but no negative weight cycles, for any pair of vertices $(u, v)$ such that there is a path from $u$ to $v$, there is a shortest path (path of least total weight) from $u$ to $v$ that has at most $n-1$ edges, where $n$ is the number of vertices in the graph.

Problem : Imagine a transportation network in which cities are linked by two modes of transportation: fast but expensive Hyperloop tubes and slow but cheap on-demand self-driving cars. Two cities may or may not be linked directly (without requiring a transfer in another city), but if they are linked by one mode they are linked by the other as well. For any pair of linked cities, the travel time is known and consistent (no congested traffic!) for both modes of transportation, and the Hyperloop is always at least as fast as the self-driving cars (and neither mode can send you back in time). Wait times and transfer times are negligible.

Suppose you have plenty of money for self-driving cars but can't afford any Hyperloop trips – except you have a one-time promotional code good for free travel between any pair of cities linked directly to each other. You need to find the fastest way to travel from your home city to some other given city (Baltimore, for example, has a great aquarium, baseball stadium, free art musuems, restaurants...). Model this problem as a graph problem, describe an efficient algorithm to solve it, and prove that your algorithm is correct (hint: if you use an existing algorithm then you don't have to repeat the proof that it is correct, but you do have to explain how your use of it results in the correct output).

Problem : Consider the following algorithm for computing a minimum spanning tree in a weighted graph $G = (V, E)$ in which all the weights are distinct and the vertices are labelled $0, 1, \ldots, n-1$.

• $A \leftarrow \emptyset$
• while the graph $(V, A)$ has more than one connected component
  • $L \leftarrow \emptyset$
  • for each connected component $C$ in $A$
    • find the minimum-weight edge $(u, v)$ where $u \in C$ and $v \not\in C$
    • $L \leftarrow L \cup \{(u, v)\}$
  • for each $(u, v) \in L$,
    • $A \leftarrow A \cup \{(u, v)\}$

• Prove that this algorithm is correct by showing that
  • $A \cup L$ is acyclic, and
  • at the time $(u, v)$ is added to $A$, it is the light weight edge across some cut that $A$ respects,
  so that, by the Light Edge Theorem (Cut Property), $A$ is always a subset of some minimum spanning tree.
• Show how to implement this algorithm in worst-case $O(m \log n)$ time and explain why your implementation runs in $O(m \log n)$ time. (This will involve choosing data structures and reasoning about the number of iterations of the loop. You need not prove that your particular implementation is correct.)

---