Question: In class we applied the minimum matching problem to matching freshmen to dorms. In terms of m and n, how long does this algorithm take?
Answer: There are n shortest-path computations. Each takes O(m log n) time. So the total time is O(mn log n).