Randomized Shortest-Path Problems: A first study Draft manuscript submitted for publication

Abstract. Suppose you have to route agents through a network from a source node to a destination node in some optimal way; for instance by minimizing the total travel cost. Nothing new up to now – you could use a standard shortestpath algorithm. Suppose, however, that you want to avoid pure deterministic routing policies in order, for instance, to allow some exploration of the network, to avoid congestion, or to avoid complete predictability of your routing strategy. In other words, the routing policy is randomized. This problem, which will be called the randomized shortest-path problem, is introduced in this paper. The global degree of randomness of the routing policy will be quantified by the expected Shannon entropy spread into the network. Then, two models, allowing to compute the optimal policy under entropy constraints, are studied. One of these two models allows to compute this optimal policy by solving a simple, usually sparse, linear system of equations. 1