Author
Listed:
- DRAGAN VASILJEVIC
(Department of Operations Management, Faculty of Organizational Sciences, University of Belgrade, Serbia)
- MILOS DANILOVIC
(Department of Operations Management, Faculty of Organizational Sciences, University of Belgrade, Serbia)
Abstract
We present two new linear algorithms for the single source shortest paths problem. The worst case running time of the first algorithm is O(m + C log C), where m is the number of edges of the input network and C is the ratio of the largest and the smallest edge weight. The pseudo-polynomial character of the time dependence can be overcome by the fact that Dijkstra's kind of shortest paths algorithms can be implemented "from the middle", when the shortest paths to the source are known in advance for a subset of the network vertices. This allows the processing of a subset of the edges with the proposed algorithm and processing of the rest of the edges with any Dijkstra's kind algorithm afterwards. Partial implementation of the algorithm enabled the construction of a second, highly efficient and simple linear algorithm. The proposed algorithm is efficient for all classes of networks and extremely efficient for networks with small C. The decision which classes of networks are most suitable for the proposed approach can be made based on simple parameters. Experimental efficiency analysis shows that this approach significantly reduces total computing time.
Suggested Citation
Dragan Vasiljevic & Milos Danilovic, 2013.
"A Novel Linear Algorithm For Shortest Paths In Networks,"
Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 30(02), pages 1-25.
Handle:
RePEc:wsi:apjorx:v:30:y:2013:i:02:n:s0217595912500546
DOI: 10.1142/S0217595912500546
Download full text from publisher
As the access to this document is restricted, you may want to
for a different version of it.
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:apjorx:v:30:y:2013:i:02:n:s0217595912500546. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.