Dijkstra Path Planning

So, what is Dijkstra* exactly?

Dijkstra’s algorithm is a popular algorithm for finding the shortest path between two nodes in a weighted graph. It is more efficient than BFS and DFS but lesser than A*.

The algorithm works by starting at the initial node and exploring its neighbors, keeping track of the total cost of reaching each neighbor. It then moves to the neighbor with the lowest cost and continues the process until it reaches the destination node. The algorithm guarantees that the shortest path is found, as long as all edge weights are non-negative.

It is commonly used in robotics and network routing.

The above map shows the nodes represented in pink circles and the values on the path denote the cost of each path. Using a combination of the costs and node value, we need to find the shortest path for each of them.

---

ENPM 661 Path Planning Project

• Dijkstra

Specific to my project for ENPM661, we were given a field that contains obstacles of a certain size and we need to optimize the algorithm so traversal is quickest from user-given input of the start and end node.

The assumptions for the following project are as follows:

1. The cost for each movement up, down, left and right is 1, however, any diagonal movement cost is 1.4
2. The obstacle needs to have a clearance of 5mm from each obstacle and wall.

The condition specific to this project involves movement in the following direction (total 8) as shown in the diagram below:

Enter source coordinates: 0,0

Enter destination coordinates: 10,10

The final output of the Dijkstra Path Planning is as follows: