Improved Floyd-Warshall Algorithm for Solving Travelling Salesman Problem

Abstract

The shortest path problem is a fundamental challenge in graph theory, focused on identifying the most efficient routes between nodes in a network. It stands as one of the extensively researched combinatorial optimization problems. In this paper, we explained the fundamental concepts of shortest path algorithms, with a particular emphasis on Floyd Warshall algorithm. We apply the algorithm and showed how this algorithm can be effectively employed to determine the shortest path in various scenarios. Furthermore, this paper addresses real-life applications, particularly focusing on the traveling salesman problem. Individuals often have the option to travel along different routes to reach their destination. However, selecting suboptimal routes can result in time-consuming journeys. To tackle this issue, we apply the Floyd Warshall algorithm to solve the traveling salesman problem (TSP). Additionally, we demonstrate the enhancement of the Floyd Warshall algorithm's efficiency for TSP using the rectangular algorithm. This paper concludes with a comparative analysis between the original and improved Floyd Warshall algorithms, emphasizing the computational reduction achieved through the proposed enhancements.

Jagannath University Journal of Science, Volume 11, Number 1, June 2024, pp. 45−52