{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T15:47:54Z","timestamp":1762444074645},"reference-count":14,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5123,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Consider the problem of finding the shortest paths from a node source <jats:italic>s<\/jats:italic> to a node sink <jats:italic>t<\/jats:italic> in a complete network. On any given instance of the problem, only a subset of the intermediate nodes can be used to go from <jats:italic>s<\/jats:italic> to <jats:italic>t<\/jats:italic>, the subset being chosen according to a given probability law. We wish to find an a priori path from <jats:italic>s<\/jats:italic> to <jats:italic>t<\/jats:italic> such that, on any given instance of the problem, the sequence of nodes defining the path is preserved but only the permissible nodes are traversed, the others being skipped. The problem of finding an a priori path of minimum expected length is defined as the Probabilistic Shortest Path Problem (PSPP). Note that if the network is not originally complete, the PSPP methodology can still be used if we first add each missing edge, together with a <jats:italic>deterministic<\/jats:italic> length (being defined by an alternative path using nodes that have no probability of failure). In this paper, after discussing potential applications of the PSPP, we study the complexity of this class of problems. We first show that the problem is, in general, NP\u2010hard and then we develop polynomial time procedures for special cases of it. We also consider the complexity of a related problem: the Probabilistic Minimum Spanning Tree Problem (PMSTP). Finally, we provide a discussion of the implications of the results.<\/jats:p>","DOI":"10.1002\/net.3230220607","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T13:17:16Z","timestamp":1178975836000},"page":"589-605","source":"Crossref","is-referenced-by-count":34,"title":["Shortest path problems with node failures"],"prefix":"10.1002","volume":"22","author":[{"given":"Patrick","family":"Jaillet","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"ATTI, Giornate di Lavoro 1985","author":"Andreatta G.","year":"1985"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200302"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90058-7"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"e_1_2_1_8_2","volume-title":"Computers and Intractibility: A Guide to the Theory of NP\u2010completeness","author":"Garey M.","year":"1979"},{"key":"e_1_2_1_9_2","unstructured":"P.Jaillet The Probabilistic Traveling Salesman Problems. Technical Report 185 Operations Research Center MIT Cambridge MA (1985)."},{"key":"e_1_2_1_10_2","volume-title":"Stochastics in Combinatorial Optimization","author":"Jaillet P.","year":"1987"},{"key":"e_1_2_1_11_2","series-title":"NATO ASI Series F. 38","volume-title":"Flow Control of Congested Network","author":"Jaillet P.","year":"1987"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.6.929"},{"key":"e_1_2_1_13_2","volume-title":"Vehicle Routing: Methods and Studies","author":"Jaillet P.","year":"1988"},{"key":"e_1_2_1_14_2","volume-title":"Urban Operations Research","author":"Larson R.","year":"1981"},{"key":"e_1_2_1_15_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C.","year":"1982"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T03:56:26Z","timestamp":1698119786000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,10]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1992,10]]}},"alternative-id":["10.1002\/net.3230220607"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220607","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,10]]}}}