Solution: Shortest Paths

Task

You just discovered your best friend from elementary school on Twitbook. You both want to meet as soon as possible, but you live in two different cites that are far apart. To minimize travel time, you agree to meet at an intermediate city, and then you simultaneously hop in your cars and start driving toward each other. But where exactly should you meet? You are given a weighted graph $G = (V, E)$, where the vertices $V$ represent cities and the edges $E$ represent roads that directly connect cities. Each edge $e$ has a weight $w(e)$ equal to the time required to travel between the two cities. You are also given a vertex $p$, representing your starting location, and a vertex $q$, representing your friend’s starting location. To find the optimal meeting point for two people traveling along a weighted graph, we can use Dijkstra’s algorithm. We start by computing the shortest paths from both the starting vertices $p$ and $q$ to every other vertex in the graph. Then, we iterate through all the vertices in the graph and compute the sum of the shortest path distances from $$ ...