基于Floyd算法的多重最短路问题的改进算法

doi:10.11896/j.issn.1002-137X.2017.05.041

摘要/Abstract

摘要： 路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。

关键词: 无向图,Floyd算法,多重等价最短路

Abstract: Find the shortest path is the core of the path analysis,which is the fundamental problem of the network ana-lysis.Floyd algorithm is one of the most classical algorithms to solve the shortest path problem.Through analyzing practical problems,there maybe exist multiple shortest paths with the same weight that the Floyd algorithm are not addressed.This paper designed the multi-shortest paths algorithm for undirected graph based on Floyd algorithm and offered an example to exam the correctness of the algorithm.The experimental results show that the algorithm can effectively solve the problem of muti-shortest paths.

Key words: Undirected graph,Floyd algorithm,Muti-shortest path

左秀峰,沈万杰. 基于Floyd算法的多重最短路问题的改进算法[J]. 计算机科学, 2017, 44(5): 232-234. https://doi.org/10.11896/j.issn.1002-137X.2017.05.041

ZUO Xiu-feng and SHEN Wan-jie. Improved Algorithm about Muti-shortest Path Problem Based on Floyd Algorithm[J]. Computer Science, 2017, 44(5): 232-234. https://doi.org/10.11896/j.issn.1002-137X.2017.05.041

参考文献

[1] DIJKSTRA EW.A Note on Two Problems in Connection with Graphs[J].Numerische Mathematics,1959,1(1):269-271.
[2] FLOYD R W.Shortest Path[J].Communications of the Asso-ciation for Computing Machinery,1962,15(6):245.
[3] NICHOLSON T A J.Finding the shortest route between twopoints in a network[J].Computer Journal,1966,9(3):275-280.
[4] DANTZIG G B.Linear Programming and Extensions[J].Undergraduate Texts in Mathematics,1963,34(136):242-243.
[5] HART P E,NILSSON N J,RAPHAEL B.A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J].IEEE Transactions on Systems Science & Cybernetics,1968,4(2):100-107.
[6] GUTMAN R J.Reach-Based Routing:A New Approach to Shor-test Path Algorithms Optimized for Road Networks[C]∥Workshop on Algorithm Engineering & Experiments.2004:100-111.
[7] LIU J M,MA S F,MA S Q.Computation method of the dynamicshortest path based on improved-Dijkstra algorithm[J].Systems Engineering-Theory&Practice,2011,31(6):1153-1157.(in Chinese).刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践,2011,31(6):1153-1157.
[8] ZHANG D Q,WU G L,LIU D F.Accelerated and optimized method of Floyd algorithm to find out shortest path[J].Computer Engineering and Applications,2009,45(17):41-43,46.(in Chinese) 张德全,吴果林,刘登峰.最短路问题的Floyd加速算法与优化[J].计算机工程与应用,2009,45(17):41-43,6.
[9] LIN L,YAN C G,JIANG C J,et al.Complexity and Approximate Algorithm of Shortest Paths in Dynamics Networks[J].Chinese Journal of Computers,2007,30(4):608-614.(in Chinese) 林澜,闫春钢,蒋昌俊,等.动态网络最短路问题的复杂性与近似算法[J].计算机学报,2007,30(4):608-614.
[10] LONG G Z,YANG J J.Improved Algorithm of Short-Cut[J].Systems Engineering and Electronics,2002,24(6):106-108.(in Chinese) 龙光正,杨建军.改进的最短路算法[J].系统工程与电子技术,2002,24(6):106-108.
[11] ZHENG S F,CAO J D,LIAN X M.Sector Dijkstra algorithm for shortest routes between customers in complex roa networks[J].Journal of Tsinghua University(Science and Technology) 2009,49(11):1834-1837.(in Chinese) 郑四发,曹剑东,连小珉.复杂路网下多客户间最短路径的扇面Dijkstra算法[J].清华大学学报(自然科学版),2009,49(11):1834-1837.
[12] HOFFMAN W,PAVLEY R.A Method for the Solution of the Nth Best Path Problem[J].Journal of the ACM,1959,6(4):506-514.
[13] XU T,DING X L,LI J F.Review on K shortest paths algo-rithms[J].Computer Engineering and Design,2013,34(11):3900-3906.(in Chinese) 徐涛,丁晓璐,李建伏.K最短路径算法综述[J].计算机工程与设计,2013,34(11):3900-3906.
[14] WANG L X,GAO W.Optimization on mutiple shortest path algorithm[J].Sci/Tech Information Development & Economy,1999(2):22-23.(in Chinese) 王丽星,郜巍.多条最短路算法的优化[J].科技情报开发与经济,1999(2):22-23.
[15] WANG Z J,HAN W Y,LI Y J.Shortest path problem with multiple shortest paths[J].Journal of Harbin Institute of Technology,2010,42(9):1428-1431.(in Chinese) 王志坚,韩伟一,李一军.具有多条最短路径的最短路问题[J].哈尔滨工业大学学报,2010,42(9):1428-1431.
[16] WANG S X,LI A Y.Multi-adjacent-vertexes an Multi-shortest-paths Problem of Dijkstra Algorithm[J].Computer Science,2014,41(6):217-224.(in Chinese) 王树西,李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学,2014,41(6):217-224.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed