A hybrid technique for single-source shortest path-based on A* algorithm and ant colony optimization

Abstract

In the single-source shortest path (SSSP) problem, the shortest paths from a source vertex v to all other vertices in a graph should be executed in the best way. A common algorithm to solve the (SSSP) is the A* and Ant colony optimization (ACO). However, the traditional A* is fast but not accurate because it does not calculate all node’s distance of the graph. Moreover, it is slow in path computation. In this paper, we propose a new technique that consists of a hybridizing of A* algorithm and ant colony optimization (ACO). This solution depends on applying the optimization on the best path. For justification, the proposed algorithm has been applied to the parking system as a case study to validate the proposed algorithm performance. First, A*algorithm generates the shortest path in faster time complexity. ACO will optimize this path and output the best path. The result showed that the proposed solution provides an average decreasing time complexity e is 13.5%.