A novel pseudo‐polynomial approach for shortest path problems

This article presents a novel shortest path algorithm for connected networks with nonnegative edge weights. The worst case running time of the single source shortest path version of the algorithm is O(max(m, ϵ^vs)) where m is the number of edges of the input network and ϵ^vs is the normalized eccent...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2021-09, Vol.78 (2), p.107-127
Main Authors: Danilovic, Milos, Vasiljevic, Dragan, Cvetic, Biljana
Format: Article
Language:English
Subjects:
Algorithms
buckets
Computing time
heaps
Networks
Polynomials
priority queues
Run time (computers)
Shortest-path problems
single source problem
weight ratio
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:This article presents a novel shortest path algorithm for connected networks with nonnegative edge weights. The worst case running time of the single source shortest path version of the algorithm is O(max(m, ϵ^vs)) where m is the number of edges of the input network and ϵ^vs is the normalized eccentricity of the source vertex vs. The pseudo‐polynomial nature of the time complexity is overcome with a simple speed‐up technique. The proposed approach can be implemented on a wide class of shortest path problems. Approximate solutions can be easily maintained in the preprocessing phase. An experimental efficiency analysis shows that the proposed approach outperforms existing algorithms in total computing time. The proposed algorithm is efficient for all classes of networks and particularly for networks with small diameter.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.22027