Performance of shortest path algorithm based on parallel vertex traversal | Zendy

Mihailo Vesović | Zendy; Aleksandra Smiljanić | Zendy; Dušan Kostić | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Performance of shortest path algorithm based on parallel vertex traversal

Author(s) -

Mihailo Vesović,

Aleksandra Smiljanić,

Dušan Kostić

Publication year - 2016

Publication title -

serbian journal of electrical engineering

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.133

H-Index - 5

eISSN - 2217-7183

pISSN - 1451-4869

DOI - 10.2298/sjee1601031v

Subject(s) - shortest path problem , k shortest path routing , yen's algorithm , constrained shortest path first , shortest path faster algorithm , computer science , tree traversal , dijkstra's algorithm , private network to network interface , algorithm , widest path problem , euclidean shortest path , speedup , vertex (graph theory) , network topology , parallel computing , routing (electronic design automation) , theoretical computer science , link state routing protocol , graph , computer network , routing protocol

Shortest path algorithms for different applications, such as Internet routing, VLSI design and so on are used. Dijkstra and Bellman-Ford are commonly used shortest path algorithms which are typically implemented in networks with hundreds of nodes. However, scale of shortest path problems is increasing, and more efficient algorithms are needed. With the development of multicore processors, one natural way to speedup shortest path algorithms is through parallelization. In this paper, we propose a novel shortest path algorithm with parallel vertex transversal, and compare its speed with standard solutions in datacenter topologies

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research