Prim’s Algorithm for Robot Path Planner in C++
Prim’s algorithm is a greedy algorithm that can be applied to robot path planners. Depending on the unit of the edges, the algorithm computes the shortest path between the node, if the distance is given.
In this article, I will display practical examples and implementation of this algorithm in C++.
The article gives you an excellent opportunity to understand the intuition of the algorithm in action and software deployment.
The source code for this article in C++ can be found on my GitHub.
I divided implementation into two parts. One part builds the spanning tree of the given graph and the other finds the shortest path between given nodes.
The most important feature of the spanning tree used for robot path planning is that it does not have graph cycles.
The following figures give you general intuition over the implementation.
In the first phase, bearing in mind the deployment algorithm in C++, the most important is to understand how to transit to the next node (we simply choose the minimum value from the visited nodes; while the minimum value is identified we can verify which pair of nodes this value refer to). Please consider the figure and understand the algorithm.
In the second phase, the pairs identified in the first phase need to be connected in order to find the way from the start node with the goal. In the code deployed I used a simple array of vectors. The position in the array refers to the parent. The vector of the array (for each parent) includes the children node of this particular parent.
Thank you for reading.
