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:
The input format is given below: (same as the UCSD Graphs course on Coursera):
- First line is the total number of points, N
- 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 |
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:
- Kruskal’s algorithm, check this page.
- Dijkstra’s algorithm, check here
Corner
Reblogged this on Corner.