Premium
Shortest paths in networks with exponentially distributed arc lengths
Author(s) -
Kulkarni V. G.
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160303
Subject(s) - shortest path problem , markov chain , constrained shortest path first , average path length , mathematics , path length , longest path problem , yen's algorithm , path (computing) , k shortest path routing , euclidean shortest path , computation , shortest path faster algorithm , node (physics) , arc length , algorithm , computer science , combinatorics , arc (geometry) , dijkstra's algorithm , graph , computer network , statistics , geometry , structural engineering , engineering , programming language
This paper develops methods for the exact computation of the distribution of the length of the shortest path from a given source node s to a given sink node t in a directed network in which the arc lengths are independent and exponentially distributed random variables. A continuous time Markov chain with a single absorbing state is constructed from the original network such that the time until absorption into this absorbing state starting from the initial state is equal to the length of the shortest path in the original network. It is shown that the state space of this Markov chain is the set of all minimal ( s, t ) cuts in the network and that its generator matrix is upper triangular. Algorithms are described for computing the distribution and moments of the length of the shortest path based on this Markov chain representation. Algorithms are also developed for computing the probability that a given ( s, t ) path is the shortest path in the network and for computing the conditional distribution of the length of a path given that it is the shortest ( s, t ) path in the network. All algorithms are numerically stable and are illustrated by several numerical examples.