SHORTEST PATHS IN STOCHASTIC NETWORKS WITH ARC LENGTHS HAVING DISCRETE-DISTRIBUTIONS

被引:15
作者
COREA, GA [1 ]
KULKARNI, VG [1 ]
机构
[1] UNIV N CAROLINA,DEPT OPERAT RES,CHAPEL HILL,NC 27514
关键词
D O I
10.1002/net.3230230305
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:175 / 183
页数:9
相关论文
共 16 条
[2]  
BEREANU B, 1966, REV ROUMAINE MATH PU, V2, P713
[3]  
COREA GA, 1989, THESIS U N CAROLINA
[4]  
Dijkstra E. W., 1959, NUMER MATH, P269, DOI DOI 10.1007/BF01386390
[5]   METHOD FOR SOLUTION OF DISTRIBUTION PROBLEM OF STOCHASTIC LINEAR-PROGRAMMING [J].
EWBANK, JB ;
FOOTE, BL ;
KUMIN, HJ .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1974, 26 (02) :225-238
[6]   ESTIMATING NETWORK CHARACTERISTICS IN STOCHASTIC ACTIVITY NETWORKS [J].
FISHMAN, GS .
MANAGEMENT SCIENCE, 1985, 31 (05) :579-593
[7]   ALGORITHM-97 - SHORTEST PATH [J].
FLOYD, RW .
COMMUNICATIONS OF THE ACM, 1962, 5 (06) :345-345
[8]   SHORTEST PATHS IN PROBABILISTIC GRAPHS [J].
FRANK, H .
OPERATIONS RESEARCH, 1969, 17 (04) :583-&
[9]  
FREDMAN ML, 1989, J ACM, V4, P596
[10]  
HAYHURST KJ, 1990, 9007 COLL WILL MAR D