Lesson 11 of 14

Shortest Paths and Minimum Spanning Trees

Three buildings have connecting paths. A-B costs 2, B-C costs 2, and A-C costs 3. Reaching one destination cheaply and connecting every building cheaply are different problems.

   A -----3----- C
    \           /
     2         2
      \       /
          B

Travel from A to C cheaply

The direct route costs 3. Going through B costs 2 + 2 = 4. The shortest path therefore goes directly from A to C. Here, shortest means the smallest sum of edge costs.

When every weight is nonnegative, Dijkstra’s algorithm can find shortest paths:

1. Set the starting distance to zero and unknown distances to infinity.
2. Choose the unsettled vertex with the smallest current distance.
3. Reduce a neighbor’s distance if going through that vertex costs less. This update is called relaxation.
4. Continue until the reachable vertices have been processed.

After processing A, B has distance 2 and C has distance 3. The route to C through B costs 4, so C’s distance stays 3. Negative edge weights can invalidate the settling rule.

Connect every building cheaply

A spanning tree connects all vertices without a cycle. It has V-1 edges for V vertices. In a connected undirected graph, a minimum spanning tree (MST) minimizes the sum of those edge costs.

Here, choosing A-B and B-C connects all buildings for a total cost of 4. Adding A-C increases cost and creates a cycle. Traveling from A to C inside this MST costs 4, unlike the original graph’s shortest-path cost of 3.

• Kruskal’s algorithm: Consider edges from lightest upward, accepting those that do not create a cycle.
• Prim’s algorithm: Extend the connected set using the lightest edge that reaches a vertex outside it.

Check your understanding

Which problem fits installing communication lines across a city at minimum total cost? Which fits reaching school from home in minimum time?