Dynamic Algorithms for the Shortest Path Routing Problem: Learning AutomataBased Solutions

Abstract—This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the “statistical” shortest path tree in the “average ” graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the pro-posed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to ex-hibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in envi-ronments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight up-dates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally estab-lished. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking. Index Terms—Algorithm, dynamic, routing, shortest path. I