A new algorithm for the shortest‐path problem

In this article we propose a new single‐source shortest‐path algorithm that achieves the same O(n · m) time bound as the Bellman‐Ford‐Moore algorithm but outperforms it and other state‐of‐the‐art algorithms in many cases in practice. Our claims are supported by experimental evidence....

Full description

Saved in:
Bibliographic Details
Published in:Networks 2019-07, Vol.74 (1), p.16-39
Main Authors: Elmasry, Amr, Shokry, Ahmed
Format: Article
Language:English
Subjects:
admissible graph
Algorithms
combinatorial algorithms
labeling methods
negative cycles
practical efficiency
shortest paths
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article we propose a new single‐source shortest‐path algorithm that achieves the same O(n · m) time bound as the Bellman‐Ford‐Moore algorithm but outperforms it and other state‐of‐the‐art algorithms in many cases in practice. Our claims are supported by experimental evidence.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.21870