A novel pseudo-polynomial approach for shortest paths problems
Само за регистроване кориснике
2021
Чланак у часопису (Објављена верзија)
Метаподаци
Приказ свих података о документуАпстракт
This article presents a novel shortest-paths algorithm for connected networks with non-negative edge weights. The worst case running time of the Single Source Shortest Path version of the algorithm is O(max(m, (epsilon) over cap(nu(s)))) where m is the number of edges of the input network, and (epsilon) over cap(nu(s)), the normalized eccentricity of the source vertex. The pseudo-polynomial nature of the time dependence is overcome with 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.
Кључне речи:
weight ratio / single source problem / priority queues / heaps / buckets / algorithmИзвор:
Networks, 2021, 77, 3, 472-472Издавач:
- Wiley, Hoboken
DOI: 10.1002/net.21966
ISSN: 0028-3045
WoS: 000548210200001
Scopus: 2-s2.0-85105906571
Институција/група
Fakultet organizacionih naukaTY - JOUR AU - Danilović, Miloš AU - Vasiljević, Dragan AU - Cvetić, Biljana PY - 2021 UR - https://rfos.fon.bg.ac.rs/handle/123456789/2221 AB - This article presents a novel shortest-paths algorithm for connected networks with non-negative edge weights. The worst case running time of the Single Source Shortest Path version of the algorithm is O(max(m, (epsilon) over cap(nu(s)))) where m is the number of edges of the input network, and (epsilon) over cap(nu(s)), the normalized eccentricity of the source vertex. The pseudo-polynomial nature of the time dependence is overcome with 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. PB - Wiley, Hoboken T2 - Networks T1 - A novel pseudo-polynomial approach for shortest paths problems EP - 472 IS - 3 SP - 472 VL - 77 DO - 10.1002/net.21966 UR - conv_2340 ER -
@article{ author = "Danilović, Miloš and Vasiljević, Dragan and Cvetić, Biljana", year = "2021", abstract = "This article presents a novel shortest-paths algorithm for connected networks with non-negative edge weights. The worst case running time of the Single Source Shortest Path version of the algorithm is O(max(m, (epsilon) over cap(nu(s)))) where m is the number of edges of the input network, and (epsilon) over cap(nu(s)), the normalized eccentricity of the source vertex. The pseudo-polynomial nature of the time dependence is overcome with 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.", publisher = "Wiley, Hoboken", journal = "Networks", title = "A novel pseudo-polynomial approach for shortest paths problems", pages = "472-472", number = "3", volume = "77", doi = "10.1002/net.21966", url = "conv_2340" }
Danilović, M., Vasiljević, D.,& Cvetić, B.. (2021). A novel pseudo-polynomial approach for shortest paths problems. in Networks Wiley, Hoboken., 77(3), 472-472. https://doi.org/10.1002/net.21966 conv_2340
Danilović M, Vasiljević D, Cvetić B. A novel pseudo-polynomial approach for shortest paths problems. in Networks. 2021;77(3):472-472. doi:10.1002/net.21966 conv_2340 .
Danilović, Miloš, Vasiljević, Dragan, Cvetić, Biljana, "A novel pseudo-polynomial approach for shortest paths problems" in Networks, 77, no. 3 (2021):472-472, https://doi.org/10.1002/net.21966 ., conv_2340 .