“A Comparison In Different Types Of Shortest Path Algorithms and using best algorithm their Implementation in Shortest Route network system”

Abstract

To Finding the shortest path in a network is a commonly encountered problem. For example you want to reach a target in the real world via the shortest path or in a computer network a network package should be efficiently routed through the network. This theory describes the problem modeled as a graph and the Dijkstra algorithm is used to solve the problem.

 In computer networks, the routing is based on the shortest path problem. This will help in minimizing the overall costs of setting up computer networks. New technologies such as map-related systems are also applying the shortest path problem. This paper’s main objective is to evaluate the Dijkstra’s Algorithm, Floyd-Warshall Algorithm, Bellman-Ford Algorithm, and Genetic Algorithm (GA) in solving the shortest path problem. A short review is performed on the various types of shortest path algorithms. Further explanations and implementations of the algorithms are illustrated in graphical forms to show how each of the algorithms works. A framework of the GA for finding optimal solutions to the shortest path problem  is  presented. The results of evaluating the Dijkstra’s, Floyd-Warshall and Bellman-Ford algorithms along with their time complexity conclude the paper.