{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T06:41:19Z","timestamp":1783233679928,"version":"3.54.6"},"reference-count":15,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7345,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1986,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper develops methods for the exact computation of the distribution of the length of the shortest path from a given source node <jats:italic>s<\/jats:italic> to a given sink node <jats:italic>t<\/jats:italic> 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 <jats:italic>time<\/jats:italic> until absorption into this absorbing state starting from the initial state is equal to the <jats:italic>length<\/jats:italic> 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 (<jats:italic>s, t<\/jats:italic>) 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 (<jats:italic>s, t<\/jats:italic>) 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 (<jats:italic>s, t<\/jats:italic>) path in the network. All algorithms are numerically stable and are illustrated by several numerical examples.<\/jats:p>","DOI":"10.1002\/net.3230160303","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T21:17:27Z","timestamp":1178918247000},"page":"255-274","source":"Crossref","is-referenced-by-count":50,"title":["Shortest paths in networks with exponentially distributed arc lengths"],"prefix":"10.1002","volume":"16","author":[{"given":"V. G.","family":"Kulkarni","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"V. G.AdlakhaandG. S.Fishman.An improved conditional Monte Carlo technique for the stochastic shortest route problem. Technical Report No. 84\u20139 Curriculum in Operations Research and Systems Analysis University of North Carolina Chapel Hill N. C. 27514 (1984)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.3.207"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140208"},{"key":"e_1_2_1_5_2","unstructured":"G. S.Fishman.Estimating critical path and arc probabilities in stochastic activity networks. TR\u201083\/5 Curriculum in Operations Research and Systems Analysis University of North Carolina Chapel Hill N. C. 27514 (1983)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.4.583"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90005-1"},{"key":"e_1_2_1_8_2","article-title":"Markov and Markov\u2010regenerative PERT networks","author":"Kulkarni V. G.","journal-title":"Operations Res."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.13.1.46"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(76)90017-4"},{"key":"e_1_2_1_11_2","first-page":"14","article-title":"Application of multi\u2010channel queing results to the analysis of conveyor systems","volume":"17","author":"Pritsker A. A. B.","year":"1966","journal-title":"J. Indust. Eng."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.3.516"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.3.237"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4754(79)90007-7"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.5.1122"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322220"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230160303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230160303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T02:17:42Z","timestamp":1697854662000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230160303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,9]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1986,9]]}},"alternative-id":["10.1002\/net.3230160303"],"URL":"https:\/\/doi.org\/10.1002\/net.3230160303","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,9]]}}}