Shortest paths in stochastic networks with ARC lengths having discrete distributions

✍ Scribed by Gehan A. Corea; Vidyadhar G. Kulkarni

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 688 KB
• Volume: 23
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230230305

✦ Synopsis

Abstract

In this work, we compute the distribution of L*, the length of a shortest (s, t) path, in a directed network G with a source node s and a sink node t and whose arc lengths are independent, nonnegative, integer valued random variables having finite support. We construct a discrete time Markov chain with a single absorbing state and associate costs with each transition such that the total cost incurred by this chain until absorption has the same distribution as does L*. We show that the transition probability matrix of this chain has an upper triangular structure and exploit this property to develop numerically stable algorithms for computing the distribution of L* and its moments. All the algorithms are recursive in nature and are illustrated by several examples. © 1993 by John Wiley & Sons, Inc.