Paper Info
Title
Finding The Shortest Path In Stochastic Graphs Using Learning Automata And Adaptive Stochastic Petri Nets
Abstract
Shortest path problem in stochastic graphs has been recently studied in the literature and a number of algorithms has been provided to find it using varieties of learning automata models. However, all these algorithms suffer from two common drawbacks: low speed and lack of a clear termination condition. In this paper, we propose a novel learning automata-based algorithm for this problem which can speed up the process of finding the shortest path using parallelism. For this parallelism, several traverses are initiated, in parallel, from the source node towards the destination node in the graph. During each traverse, required times for traversing from the source node up to any visited node are estimated. The time estimation at each visited node is then given to the learning automaton residing in that node. Using different time estimations provided by different traverses, this learning automaton gradually learns which neighbor of the node is on the shortest path. To set a condition for the termination of the proposed algorithm, we analyze the algorithm using a recently introduced model, Adaptive Stochastic Petri Net (ASPN-LA). The results of this analysis enable us to establish a necessary condition for the termination of the algorithm. To evaluate the performance of the proposed algorithm in comparison to the existing algorithms, we apply it to find the shortest path in six different stochastic graphs. The results of this evaluation indicate that the time required for the proposed algorithm to find the shortest path in all graphs is substantially shorter than that required by similar existing algorithms.
Year
DOI
Venue
2017
10.1142/S0218488517500180
INTERNATIONAL JOURNAL OF UNCERTAINTY FUZZINESS AND KNOWLEDGE-BASED SYSTEMS
Keywords
Field
DocType
Stochastic graphs, the shortest path problem, learning automata, adaptive stochastic petri net based on learning automata
Learning automata,Constrained Shortest Path First,Theoretical computer science,Artificial intelligence,Shortest Path Faster Algorithm,Longest path problem,K shortest path routing,Discrete mathematics,Shortest path problem,Stochastic Petri net,Mathematics,Machine learning,Euclidean shortest path
Journal
Volume
Issue
ISSN
25
3
0218-4885
Citations 
PageRank 
References 
8
0.44
15
Authors
3
Name
Order
Citations
PageRank
S. Mehdi Vahidipour1392.89
Mohammad Reza Meybodi2166496.57
Mehdi Esnaashari313110.37