For a given set of randomly distributed points in 2-dimensional space, Prim’s algorithm is utilized to find the minimum total distance from a randomly selected origin point (P_origin). Here, the progress of how the distances are selected by the algorithm at the first instant along the way to reach the minimum spanning tree (MST) is shown. The algorithm is written in C++, visualization is done via Python, video editing by Blender.

Also, for those who want to run their algorithm for the same set of points in this video, you can download the input files here: Dropbox path:

Then for the next N lines, we have two columns for x and y locations of points (x,y)

The first point is taken as the origin point

Input file format

Sample input file

Npoints
x1 y1
...
xN yN

3
1 2
4 5
2 3

Final minimum spanning tree snapshots for several random point distributions:

Minimum Spanning Trees as overlaid on West Coast of US and San Francisco region are also shown in the following figures. The geo-locations of the nodes are obtained from DIMACS and Python’s Basemap module is utilized for background maps.

Also using gmplot same MST plot overlaid on Google Maps:

## One thought on “Prim’s Algorithm Progression Animation for randomly distributed points”