Program of Searching the Shortest Path in the Presence of Random Traffic Jams on the Road

The shortest path search in the presence of traffic jams on the road is in demand today. The objective of this work is to present a method that uses information about the probability of possible values of speed on all sections of the road and calculates the travel time along the shortest route in different cases: average, the best, the worst and theoretical. The first three values of time are computed in a series of computational experiments, during which the values of velocities on all sections of the road are obtained using a pseudo- random number generator with the distribution given by the velocity and probability matrices. The theoretical value of the travel time along the shortest route is calculated on the basis of statistical information about the speeds. The shortest path search is realized using Floyd-Warshall algorithm, Dijkstra’s algorithm and Bellman-Ford algorithm are also realized to compare the execution time of algorithms with different input data and determine the fastest algorithm. This application works with a graph that represents a road network. The application receives information about the graph and speeds between vertices of the graph from 3 files: distance matrix, speed matrix, probability matrix.