The use of the shortest path on the taxi route to the destination point can certainly reduce the cost of travel fares. This can provide benefits for taxi customers as well as for the progress of the taxi company. Airport Taxi Angkasa Pura II Kualanamu International Airport applies taxi orders through the call center. Prospective passengers who have ordered a taxi through the operator will be picked up by the taxi driver immediately. Taxis that are closer and there are no passengers will answer the call center to pick up passengers. Due to the limited information on road data, it makes taxi drivers need time to find out the shortest path to be taken in order to determine a more efficient fare. For this reason, a geographic information system to find the shortest path to determine the minimum fare to make it easier for passengers to find out the cost of travel fares. From the results of the application of data in the field, it can be seen that the A Star algorithm has succeeded in finding the shortest path to determine the minimum travel fare