Spanning Trees and Shortest Paths

Problem: Minimum Spanners

Consider the following weighted, undirected graph:

1. Come up with at least three spanning trees for this graph using the techniques discussed in the reading. Write down the collection of edges that compromises each tree.
2. When our graphs have weights, we are concerned with finding minimum spanning trees (MSTs), spanning trees whose sum-of-weights-of-edges is minimal for any spanning tree of the graph. Use Prim's algorithm as described in the reading to come up with a MST for this graph. Note the edges of your MST and the sum-of-weights of that tree. Check with an instructor that your MST is indeed the minimal one.

Problem: Jump Up, Superstar!

In the reading, we explored Dijkstra's algorithm, a fundamental technique for finding the shortest paths of a graph. Here, we explore the algorithm in more detail and then extend it to make it more appropriate for certain real world scenarios.

1. Run Dijkstra's algorithm on the graph above, starting at vertex $A$. In your write-up, give the resulting shortest paths and their costs from $A$ to every other node in the graph.

2. In many cases, weights in our graph correspond to physical distances between vertices. In these scenarios, the triangle inequality will hold between vertices. For any three vertices $a$, $b$, and $c$ that have edges between them, i.e., they form a triangle:

   $$|ab|+|bc|\ge |ac|$$

   Where $|ab|$ is the weight of edge $ab$.

   In a sentence or two, translate what the triangle inequality says with respect to the domain of vertices and lengths of paths between them.

3. In a sentence or two, explain why the graph from the previous question on spanning trees does not obey the triangle inequality.

4. In cases where the triangle inequality holds, we can take advantage of this fact by introducing a heuristic function that allows us to better prioritize the nodes we consider during Dijkstra's search. Let $h(v)$ be the straight line distance between $v$ and target $t$. For example, in the graph from part (a), if we declare our target vertex to be $I$, then:

   $$\begin{array}{rl}h(A)& =h(A)=\sqrt{2^2+2^2}=\sqrt{8}\\ h(E)& =\sqrt{1^2+1^2}=\sqrt{2}\\ h(H)& =1.\end{array}$$

   All due to the Pythagorean theorem.

   Rerun Dijkstra's on this graph to find the optimal path from $A$ to $I$. However, when you need to calculate the next node to process, rather than choosing the minimal $c(v)$, the current best-known path from $A$ to $v$, choose the vertex $v$ that minimizes:

   $$c(v)+h(v).$$

   In other words, choose the vertex $v$ that minimizes the sum of the current best-known path from $A$ to $v$ and the straight line distance from $v$ to $I$. You may stop once you have established the shortest path from $A$ to $I$.

   In your write-up, give the sequence of nodes that you visited in your modified algorithm. Also, in your write-up describe in a few sentences how the heuristic function $h(v)$ made your shortest path search more efficient.

5. This extension of Dijkstra's algorithm is called $A^{\ast }$ ("A-star") which is a common pathfinding algorithm in many contexts where the graph in question represents physical distances. In this problem, we considered a heuristic function $h(v)$, but it turns out that any heuristic function will work as long as it doesn't overestimate the actual cost to get to the goal node in the graph.

   Discuss why the heuristic function must now overestimate the actual cost of the shortest path. Specifically, what happens to Dijkstra's algorithm if the heuristic function has this bad property?