ALGORITHMS FOR FINDING THE K-SHORTEST PATHS IN A NETWORK

被引：85

作者：

SHIER, DR

机构：

[1] National Bureau of Standards, Washington, District of Columbia

来源：

NETWORKS | 1979年 / 9卷 / 03期

关键词：

D O I：

10.1002/net.3230090303

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents, within a unified framework, several new algorithms for computing k shortest paths in a network. These algorithms utilize strategies which have proved to be efficient in solving shortest path problems. In addition, a computational study was conducted to assess the effects of the different “arc processing” orders which are characteristic of each algorithm. Testing was performed using generated classes of moderately large grid, complete and random networks. Two particular algorithms emerge as the most promising among those evaluated. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company

引用

页码：195 / 214

页数：20

共 20 条

[1]

Dial R.B., Algorithm 360: Shortest Path Forest with Topological Ordering, Communications of the ACM, 12, pp. 632-633, (1969)

[2]

Dijkstra E.W., A Note on Two Problems in Connexion with Graphs, Num. Math., 1, pp. 269-271, (1959)

[3]

Dreyfus S.E., An Appraisal of Some Shortest‐Path Algorithms, Operations Research, 17, pp. 395-412, (1969)

[4]

Fox B.L., Calculating kth Shortest Paths, INFOR., 11, pp. 66-70, (1973)

[5]

Fox B.L., More on kth Shortest Paths, Communications of the ACM, 18, (1975)

[6]

Gilsinn J., Witzgall C., A Performance Comparison of Labeling Algorithms for Calculating Shortest Path Trees, Technical Note 772, (1973)

[7]

Hitchner L.E., (1968)

[8]

Lawler E.L., A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and its Application to Shortest Path Problems, Management Science, 18, pp. 401-405, (1972)

[9]

Lawler E.L., Combinatorial Optimization, (1976)

[10]

Minieka E., On Computing Sets of Shortest Paths in a Graph, Comm. ACM, 17, pp. 351-353, (1974)

← 1 2 →