What is it?

Prims Minimum Spanning Tree is an algorithm design to find the minimum span to connect all nodes in a graph. The algorithm has many uses and abstractions to solve problems but in this example I chose a very visual and real world based problem to solve.

Imagine you want to connect all the towns and villages on the map to a new hyper fast fiber optic cable. Each possible route is marked in grey and there are many 1000's of solutions to connect all the locations. One way to solve this is via brute force, calculate the length of all combinations, but this could become very inefficient very quickly.

When you play the demo above the Prims algorithm starts solving the problem (in slow motion so you can see it working).

Even tho the algorithm starts each time at a random location the final solution is always the same, the shortest length of cable needed.

How did I make it?

My first stop was the Wiki page for the basics of the algorithm. I also spent some time on Youtube, Coding Train Prims was a well spent 1/2 hour.

Next I proto-typed the basic algorithm in simple OOP style Javascript. I had already decided I wanted to do a visual demo so the next step was to make a quick tool to show the map and allow me to click on a location and connect it to others. This gave me a data set (graph) to work with.

I could now run the dataset through the Prims algorithm and visualise each step on the map by updating the branch colours. Never satisfied I tried somewhat successfully to time the algorithm to a soundtrack. Sorry it's SO LOUD!

As with most of my demos the algorithm is solved within milli-seconds, but in order to show it working I slow it down to one step every second or two.

What I used

Code Editor - VSCode

Language - Javascript / HTML / CSS

Interesting findings

In this example we consider the distance between nodes (towns) in a 2d plane. However the node connection value can also be weighted for variables such as cost of laying cable along that route. Some routes maybe more expensive or cut through areas of natural beauty. These can be easily weighted and taken into consideration during the calculations.

Prims can be used in route finders and GPS navigation devices, using weights such as road type, congestion and speed limit to define the fastest, shortest or preferred route.

Prims can be used to generate mazes. Something to work on for my A* Pathfinder Demo