Name
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. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1002/net.3230230305 | NETWORKS |
Keywords | Field | DocType |
shortest path,discrete distribution | Graph theory,Combinatorics,Shortest path problem,Markov chain,Directed graph,Stochastic process,Arc length,Probability distribution,Discrete phase-type distribution,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 3 | 0028-3045 |
Citations | PageRank | References |
8 | 2.89 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gehan A. Corea | 1 | 8 | 2.89 |
| Vidyadhar G. Kulkarni | 2 | 539 | 60.15 |