Usage of shortest path algorithm to find the most effective path

Abstract

Traffic congestion, unsuitable or insufficient infrastructure and any unavoidable circumstances on roads are the serious problems faced by people in a city. For passengers in private vehicles there are no strict limitations to take a pre-defined path.

For such cases, as there is no predefined path from one place to the destination as in public transport systems, the passenger has the freedom to find the most efficient way to the destination from the starting point. If there is facility to select any location or city as the starting point of the journey and to select the destination as the last node and to find the most efficient path within these two points their problem will be solved to some extend.

The above scenario is taken into consideration in various ways. One way is to find the shortest path between two city locations. To find the shortest path several algorithms can be used and the execution time will depend on the algorithm.

Imagine a person who used a fixed map and use one of the algorithms to find the shortest path has started his journey. But in the middle of his journey he finds out that a road in his initial map is closed for any unavoidable reason. Then he has to find the shortest path from his current location to his destination and also he has to erase or ignore the unreachable road from his map.

But in some cases the shortest path or the path with the minimum distance will not be the best solution. Minimum distance path may have heavy traffic congestion, or hills, etc. There can be a path with slightly longer distance but with no traffic and good road conditions.

Therefore in order to find the best solution for the above mentioned problem it is required to find the most effective path for the route considered. The first step was to graphically illustrate the map. The map can have cities of known co-ordinates or the distances between the cities can be known.

Also there has to be a method of introducing the weight factors for the roads. Then the final step of finding the most effective path is to choose a suitable algorithm to findthe solution. These factors are considered in the most basic scenario of finding the most effective path.

In addition I considered on how to introduce the emergency situations in roads, like accidents, road damages, traffic, etc.

In my research I tried to find a way of answering the above