Shortest paths in stochastic networks with ARC lengths having discrete distributions

From MaRDI portal
Publication:5287451





The authors consider a two-terminal directed network whose arc lengths are independent, non-negative, integer-valued random variables with finite supports. The problem is to determine the probability distribution of the shortest path length. The problem is known to be \(\# P\)-complete even for simple networks having binary distributions of arc lengths. An exact algorithm for solving the problem is presented, and is based on constructing a discrete time Markov chain whose size grows exponentially with the network size as well with the numbers of discrete points of the arc lengths. The computational complexity of the algorithm is not presented. The paper does not discuss a more practical problem of identifying a path with the highest probability of being the shortest path.











This page was built for publication: Shortest paths in stochastic networks with ARC lengths having discrete distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5287451)