Performance of shortest path algorithm based on parallel vertex traversal
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Faculty of Technical Sciences in Cacak
2016-01-01
|
| Series: | Serbian Journal of Electrical Engineering |
| Subjects: | |
| Online Access: | http://www.doiserbia.nb.rs/img/doi/1451-4869/2016/1451-48691601031V.pdf |
| _version_ | 1818507104602816512 |
|---|---|
| author | Vesović Mihailo Smiljanić Aleksandra Kostić Dušan |
| author_facet | Vesović Mihailo Smiljanić Aleksandra Kostić Dušan |
| author_sort | Vesović Mihailo |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T22:14:02Z |
| format | Article |
| id | doaj.art-91ada6114a6e418e98d2305d8efe15ab |
| institution | Directory Open Access Journal |
| issn | 1451-4869 2217-7183 |
| language | English |
| last_indexed | 2024-12-10T22:14:02Z |
| publishDate | 2016-01-01 |
| publisher | Faculty of Technical Sciences in Cacak |
| record_format | Article |
| series | Serbian Journal of Electrical Engineering |
| spelling | doaj.art-91ada6114a6e418e98d2305d8efe15ab2022-12-22T01:31:32ZengFaculty of Technical Sciences in CacakSerbian Journal of Electrical Engineering1451-48692217-71832016-01-01131314310.2298/SJEE1601031V1451-48691601031VPerformance of shortest path algorithm based on parallel vertex traversalVesović Mihailo0Smiljanić Aleksandra1Kostić Dušan2School of Electrical Engineering, BelgradeSchool of Electrical Engineering, BelgradeSchool of Electrical Engineering, BelgradeShortest 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.http://www.doiserbia.nb.rs/img/doi/1451-4869/2016/1451-48691601031V.pdfparallelizationshortest path algorithmssingle source shortest pathBellman-FordDijkstra |
| spellingShingle | Vesović Mihailo Smiljanić Aleksandra Kostić Dušan Performance of shortest path algorithm based on parallel vertex traversal Serbian Journal of Electrical Engineering parallelization shortest path algorithms single source shortest path Bellman-Ford Dijkstra |
| title | Performance of shortest path algorithm based on parallel vertex traversal |
| title_full | Performance of shortest path algorithm based on parallel vertex traversal |
| title_fullStr | Performance of shortest path algorithm based on parallel vertex traversal |
| title_full_unstemmed | Performance of shortest path algorithm based on parallel vertex traversal |
| title_short | Performance of shortest path algorithm based on parallel vertex traversal |
| title_sort | performance of shortest path algorithm based on parallel vertex traversal |
| topic | parallelization shortest path algorithms single source shortest path Bellman-Ford Dijkstra |
| url | http://www.doiserbia.nb.rs/img/doi/1451-4869/2016/1451-48691601031V.pdf |
| work_keys_str_mv | AT vesovicmihailo performanceofshortestpathalgorithmbasedonparallelvertextraversal AT smiljanicaleksandra performanceofshortestpathalgorithmbasedonparallelvertextraversal AT kosticdusan performanceofshortestpathalgorithmbasedonparallelvertextraversal |