Topics:

1- Implement Dijkstra's search algorithm on a road network graph.

2- Implement the A* search algorithm using a Euclidean heuristic on a road network graph.

We're going to be focusing on planning in Emirate of Ajman, UAE, between the two nodes given below by using open street map and compare our results with shortest path getting from open street map ( You can try different path to check the algorithm valdity)

prerequisites

We will be relying on the OSMNX library to generate Python graphs from Open Street Map (OSM) data. These graphs will be represented using the NetworkX library. Both of these links are to the documentation

Full Implementation Details

for more more details refer to Source Code

Dijkstra's Search standard algorithm

First, let's focus on Dijkstra's algorithm.

Results of Dijkstra

The following flow demonstrates the A* search algorithm (note: we have used dictonary for distance_heuristic instead of cost distance)

A* search on our map standard algorithm

Results of A* search