The goal is to implement the classic Dijkstra's shortest path  algorithm and optimize it for maps using (A*, Heap data structure). Such algorithms are widely used in  geographic information systems (GIS) including MapQuest and  GPS-based car navigation systems.It’s important to optimize Dijkstra's algorithm so  that it can  process thousands of shortest path queries for a given map. Once the  program read in (and  optionally preprocess) the map,it should solve shortest path problems in sublinear time.