Applying random algorithm to solve the problem of finding the shortest path between pairs of vertices in a graph

Abstract

Graph theory is applied to solve real-life problems such as finding the shortest route between two cities in the traffic network, making timetables, distributing radio and television stations, etc. Common algorithms to solve this problem are: Dijkstra, Floyd-Warshall, Bellman-Ford, with approximately O(n3) complexity, where n is the number of vertices in the graph. When n is large enough, the complexity O(n3) is a significant number and the execution time is very high in practice. One solution to improve the complexity of the algorithm is to apply a random algorithm to solve the problem. In this article, I present the application of the Las Vegas random algorithm to solve with complexity lower than O(n3), with experimental results the complexity is equivalent to O(n2,376).