Ứng dụng giải thuật ngẫu nhiên để giải bài toán tìm đường đi ngắn nhất giữa các cặp đỉnh trong đồ thị

Tóm tắt

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).