Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem

被引：66
|
作者：
Aini, Asghar [2 ]
Salehipour, Amir [1 ]
机构：
[1] Islamic Azad Univ, S Tehran Branch, Sch Ind Engn, Tehran, Iran
[2] Shahid Sattari Air Univ, Sch Comp Engn, Tehran 1384637945, Iran
来源：
APPLIED MATHEMATICS LETTERS | 2012年 / 25卷 / 01期
关键词：
The shortest path problem with a cycle; The Floyd-Warshall algorithm; The Rectangular algorithm;
D O I：
10.1016/j.aml.2011.06.008
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
On a network with a cycle, where at least one cycle exists, the Floyd-Warshall algorithm is one of the algorithms most used for determining the least cost path between every pair of nodes. In this work a new algorithm for this problem is developed that requires less computational effort than the Floyd-Warshall algorithm. Furthermore, we show that the basis of our algorithm is much easier to understand, which might be an advantage for educational purposes. A small example validates our algorithm and shows its implementation. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1 / 5
页数：5
相关论文
共 50 条
  • [41] Discussion on a Simplified Algorithm for the Shortest Path Problem
    Cuiyan
    Litong
    Renshupo
    2008 INTERNATIONAL WORKSHOP ON INFORMATION TECHNOLOGY AND SECURITY, 2008, : 66 - 69
  • [42] Models and algorithm for Stochastic shortest path problem
    Ji, Xiaoyu
    Proceedings of the Third International Conference on Information and Management Sciences, 2004, 3 : 320 - 325
  • [43] Solving a shortest path problem by ant algorithm
    Fan, H
    Hua, Z
    Li, JJ
    Yuan, D
    PROCEEDINGS OF THE 2004 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2004, : 3174 - 3177
  • [44] Research on algorithm for K shortest path problem
    Zhang, Yongmei
    Han, Yan
    Bo, Chengwei
    Journal of Information and Computational Science, 2004, 1 (03): : 435 - 439
  • [45] A New Practical Algorithm for the Shortest Path Problem
    Liu, Pan
    Kou, Miao Huai
    Ping, Yu Guo
    Liang, Yin
    2008 7TH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION, VOLS 1-23, 2008, : 4120 - +
  • [46] AN APPROXIMATION ALGORITHM FOR A SHORTEST DUBINS PATH PROBLEM
    Rathinam, Sivakumar
    Khargonekar, Pramod
    PROCEEDINGS OF THE ASME 9TH ANNUAL DYNAMIC SYSTEMS AND CONTROL CONFERENCE, 2016, VOL 2, 2017,
  • [47] A new algorithm for the shortest path problem with constraints
    Leng, Hong-ze
    Xie, Zheng
    Chen, Zhi
    Xu, Zhen
    PROCEEDINGS OF FIRST INTERNATIONAL CONFERENCE OF MODELLING AND SIMULATION, VOL II: MATHEMATICAL MODELLING, 2008, : 320 - 325
  • [48] An Encoding Algorithm Based on the Shortest Path Problem
    Liu, Fanghan
    Tang, Xiaobing
    Yang, Zhaohui
    2018 14TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND SECURITY (CIS), 2018, : 35 - 39
  • [49] A new algorithm for the shortest-path problem
    Elmasry, Amr
    Shokry, Ahmed
    NETWORKS, 2019, 74 (01) : 16 - 39
  • [50] Rapid Physarum Algorithm for shortest path problem
    Zhang, Xiaoge
    Zhang, Yajuan
    Zhang, Zili
    Mahadevan, Sankaran
    Adamatzky, Andrew
    Deng, Yong
    APPLIED SOFT COMPUTING, 2014, 23 : 19 - 26
12345