Algorithms Detour - Shortest Path

Find the best path through town. The lesson teaches future computer programmers about networks and paths in graph theory. They develop a network of their towns to determine the most efficient path to visit each of their homes.

This optional lesson introduces the class to the idea of a minimum spanning tree. The activity focuses on determining an algorithm that will find the most efficient path in a network to transfer data. 

As an introduction to Steiner Trees, class members are challenged to find the shortest paths to connect multiple points. The teacher introduces the problem by showing how to connect three points. Groups then go outside and construct a...

Your routers don't seem to be routing correctly. To figure out why, pupils act like routers, talk to their direct connects in order to determine as much information about the simulated network as possible. As they learn more about...

What is the most efficient way to ensure everyone is connected? Individual pupils determine the least expensive route to pave roads in a fictional city. In doing so, they learn to find the minimal spanning tree for the situation. They...

Introduce your class to the concept of creating phylogenetic trees by playing a game of Telephone. Participants create a mixed-up message and through the use of distance matrices, the evolution of the message is recreated.