Introduction

Dijkstra's algorithm helps you find the shortest paths through an existing network.  But, what happens if you only have the nodes?  Which network connections should you select so that you can wire together all of the computers for the minimum cost?  In this context, minimum cost implies no redundant links -- there is exactly one route to get to each computer (not safe, but you get what you pay for).  Effectively, you want to find the minimum-cost spanning tree for your computers, and this problem can be solved by Prim's algorithm.
 

Resources

• To see Prim's algorithm in action, try this example.  Notice that on each step, the edge that connects to an unvisited node is selected.  The minimum-cost spanning tree is redrawn to highlight how the remaining edges are discarded.
• If you would like an example that highligths which nodes can be selected next, follow this link and try the applet demos.  The blue edges are part of the minimum-cost spanning tree, and the red edges show which edges can be selected next.
• To create your own graphs for Prim's algorithm, try this example.  Click in the white space to draw nodes (for a complete graph).  The animation then builds the minimum-cost spanning tree based on physical distance.