This paper presents the first Learning Automaton solution to the Dynamic Single Source Shortest Path Problem. It involves finding the shortest path in a single-source stochastic graph, where there are continuous probabilistically- based updates in edge-weights. The algorithm is a few orders of magnitude superior to the existing algorithms. It can be used to find the shortest path within the "statistical" average graph, which converges irrespective of whether there are new changes in edge-weights or not. On the other hand, the existing algorithms will fail to exhibit such a behavior and would recalculate the affected shortest paths after each weight change. The algorithm can be extremely useful in application domains including transportation, strategic planning, spatial database systems and networking.

Additional Metadata
Keywords Dynamic Shortest Paths, Intelligent Systems, Learning Automata
Conference 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2004
Citation
Misra, S. (S.), & Oommen, J. (2004). Stochastic learning automata-based dynamic algorithms for the single source shortest path problem. In Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) (pp. 239–248).