{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T09:45:35Z","timestamp":1751622335874,"version":"3.32.0"},"reference-count":18,"publisher":"Wiley","issue":"9","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4442,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1994,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of finding shortest paths arises in many contexts; testing restoration algorithms and developing design packages for large telecommunications networks are two cases where the simple task of finding sets of restoration paths can consume up to 95 per cent of the execution time of an application program. This paper presents experimental studies of several well\u2010known shortest\u2010paths algorithms adapted to the task of finding the k\u2010successively\u2010shortest link\u2010disjoint replacement paths for restoration in a telecommunications network with n nodes. The implementations range in complexity from<jats:italic>O<\/jats:italic>(kn<jats:sup>2<\/jats:sup>) when based on Dijkstra's original method, through several improvements to an efficient implementation of<jats:italic>O<\/jats:italic>(kn[v+long<jats:italic>n<\/jats:italic>]) complexity, and finally to an<jats:italic>O<\/jats:italic>(kn) implementation for the special case of edge\u2010sparse graphs with small integer edge weights. Here v is the maximum degree of a node in the network. Several alternatives were tested during the course of these studies, particularly with a view to minimizing the number of heap updates, These alternatives are possible because we are searching for several paths between a given pair of nodes, rather than just one path between one or more pairs of nodes. Two fairly straightforward changes yield a decrease in execution time, whereas a more complex heap management strategy consumes as much time in the added code as it releases from the main routine. Experimental results confirm the theoretical complexity of q k n log n) and demonstrate a speed\u2010up of nearly an order of magnitude over the simpler<jats:italic>O<\/jats:italic>(kn<jats:sup>2<\/jats:sup>) implementation in the largest networks tested. The optimized implementation is recommended for planning and operational applications of k\u2010shortest paths rerouting for telecommunications network restoration and restorable network design. If hop counts or small integer link weights can be used to measure distances, then the qkn) implementation is recommended, as typical telecommunications networks are edge\u2010sparse.<\/jats:p>","DOI":"10.1002\/spe.4380240904","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T17:06:40Z","timestamp":1163783200000},"page":"823-834","source":"Crossref","is-referenced-by-count":27,"title":["Optimized<i>k<\/i>\u2010shortest\u2010paths algorithm for facility restoration"],"prefix":"10.1002","volume":"24","author":[{"given":"M. H.","family":"Macgregor","sequence":"first","affiliation":[]},{"given":"W. D.","family":"Grover","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"W. D.Grover \u2018Selfhealing networks\u2014a distributed algorithm for k\u2010shortest link\u2010disjoint paths in a multi\u2010graph with applications in real time network restoration\u2019 Ph.D. Thesis University of Alberta Department of Electrical Engineering 1989."},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"H.Komine T.Chujo T.Ogura K.MiyazakiandT.Soejima \u2018A distributed restoration algorithm for multiple\u2010link and node failures of transport networks\u2019 Proc. IEEE Globecom 90 1990 pp.459\u2013463.","DOI":"10.1109\/GLOCOM.1990.116554"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"C. H.YangandS.Hasegawa \u2018FITNESS: a failure immunization technology for network service survivability\u2019 Proc. IEEE Globecom '88 1988 pp.1549\u20131554.","DOI":"10.1109\/GLOCOM.1988.26082"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/49.64910"},{"issue":"1","key":"e_1_2_1_6_2","first-page":"88","article-title":"Comparison of k\u2010shortest paths and maximum flow routing for network facility restoration","volume":"12","author":"Dunn D. A.","year":"1994","journal-title":"IEEE JSAC Special Issue on Integrity of Public Telecommunications Networks"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"B. D.Venables W. D.GroverandM. H.MacGregor \u2018Two strategies for spare capacity placement (SCP) in mesh restorable networks\u2019 Proc. IEEE ICC '93 Geneva May1993 pp.267\u2013271.","DOI":"10.1109\/ICC.1993.397269"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140208"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2514.2515"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094690"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_13_2","unstructured":"E. F.Moore \u2018The shortest path through a maze\u2019 Proc. Int. Symp. Switching Theory Cambridge Mass 1959 pp.285\u2013292."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321927"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/26.2815"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040204"},{"volume-title":"Fundamentals of Computer Algorithms","year":"1978","author":"Horowitz E.","key":"e_1_2_1_17_2"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_19_2","unstructured":"D. A.Dunn W. D.GroverandM. H.MacGregor \u2018Development and use of a random network synthesis tool with controlled connectivity statistics\u2019 TRLabs WP\u201090\u201310 August1990."}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380240904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380240904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T23:53:20Z","timestamp":1736639600000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380240904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":18,"journal-issue":{"issue":"9","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["10.1002\/spe.4380240904"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380240904","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"type":"print","value":"0038-0644"},{"type":"electronic","value":"1097-024X"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}