A robot machine is going to navigate through a series of cave connected by straight tunnels (Please see image below). It starts navigating from the A to the last cave G. Finding a shorter route is better. Some tunnels can only be navigated in one direction. Arrows are showing which cave can be reached from which other cave. For example from cave D to B is possible, however from cave B to D is not possible. All the coordinates are given in the picture. The distance between any two caves is the Euclidean distance.

Solve this question using;

a. Breadth-First Search

b. Dijkstra algorithm

c. A* search algorithm

Note:Please show all the steps and calculations.

\f