Shortest paths in stochastic networks with ARC lengths having discrete distributions
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.
- Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
- The shortest-path problem for graphs with random arc-lengths
- Least possible time paths in stochastic, time-varying networks.
- A new approach to determine the critical path in stochastic activity network
- Global optima results for the Kauffman \(NK\) model
- Improved sliding shortest path algorithm: performance analysis
- Shortest paths in a lattice network: A comparative study
- Network reliability: Heading out on the highway
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)