All-Pairs Shortest Paths Algorithm for Regular 2D Mesh Topologies
Апстракт
Motivated by the large number of vertices that future technologies will put in the front of path-search algorithms, and inspired by highly regular 2D mesh structures that exist in the domain applications, in this paper we propose a new allpairs shortest paths algorithm, for any given regular 2D mesh topology, with complexity O(vertical bar V vertical bar(2)), where vertical bar V vertical bar is the number of vertices in the graph. The proposed algorithm can achieve better runtime than other known algorithms at the cost of narrowing the scope of the graphs that it can process to the graphs with regular 2D topology. The algorithm is developed into formalism by algebraic transformations in tropical algebra of the well-known Floyd-Warshall's algorithm. First we prove the equivalency of the Floyd-Warshall's algorithm and its tropical algebraic representation, and put the transformations of the algorithm into the algebraic domain. Secondly, having in mind the structure of the target class o...f graphs, we transform the original algorithm in the algebraic domain and develop a simple, low-complexity iterative algorithm for all-pairs shortest paths calculation. Decreasing of computational complexity can contribute to better exploitation of the algorithm in the wide range of applications from hardware design in new emerging technologies to big data problems in information technologies.
Кључне речи:
tropical algebra / graph algorithms / algorithm designИзвор:
Journal of Universal Computer Science, 2016, 22, 11, 1437-1455Издавач:
- IICM
Колекције
Институција/група
Mašinski fakultetTY - JOUR AU - Cirić, Vladimir AU - Cvetković, Aleksandar AU - Milentijević, Ivan AU - Vojinović, Oliver PY - 2016 UR - https://machinery.mas.bg.ac.rs/handle/123456789/2355 AB - Motivated by the large number of vertices that future technologies will put in the front of path-search algorithms, and inspired by highly regular 2D mesh structures that exist in the domain applications, in this paper we propose a new allpairs shortest paths algorithm, for any given regular 2D mesh topology, with complexity O(vertical bar V vertical bar(2)), where vertical bar V vertical bar is the number of vertices in the graph. The proposed algorithm can achieve better runtime than other known algorithms at the cost of narrowing the scope of the graphs that it can process to the graphs with regular 2D topology. The algorithm is developed into formalism by algebraic transformations in tropical algebra of the well-known Floyd-Warshall's algorithm. First we prove the equivalency of the Floyd-Warshall's algorithm and its tropical algebraic representation, and put the transformations of the algorithm into the algebraic domain. Secondly, having in mind the structure of the target class of graphs, we transform the original algorithm in the algebraic domain and develop a simple, low-complexity iterative algorithm for all-pairs shortest paths calculation. Decreasing of computational complexity can contribute to better exploitation of the algorithm in the wide range of applications from hardware design in new emerging technologies to big data problems in information technologies. PB - IICM T2 - Journal of Universal Computer Science T1 - All-Pairs Shortest Paths Algorithm for Regular 2D Mesh Topologies EP - 1455 IS - 11 SP - 1437 VL - 22 UR - https://hdl.handle.net/21.15107/rcub_machinery_2355 ER -
@article{ author = "Cirić, Vladimir and Cvetković, Aleksandar and Milentijević, Ivan and Vojinović, Oliver", year = "2016", abstract = "Motivated by the large number of vertices that future technologies will put in the front of path-search algorithms, and inspired by highly regular 2D mesh structures that exist in the domain applications, in this paper we propose a new allpairs shortest paths algorithm, for any given regular 2D mesh topology, with complexity O(vertical bar V vertical bar(2)), where vertical bar V vertical bar is the number of vertices in the graph. The proposed algorithm can achieve better runtime than other known algorithms at the cost of narrowing the scope of the graphs that it can process to the graphs with regular 2D topology. The algorithm is developed into formalism by algebraic transformations in tropical algebra of the well-known Floyd-Warshall's algorithm. First we prove the equivalency of the Floyd-Warshall's algorithm and its tropical algebraic representation, and put the transformations of the algorithm into the algebraic domain. Secondly, having in mind the structure of the target class of graphs, we transform the original algorithm in the algebraic domain and develop a simple, low-complexity iterative algorithm for all-pairs shortest paths calculation. Decreasing of computational complexity can contribute to better exploitation of the algorithm in the wide range of applications from hardware design in new emerging technologies to big data problems in information technologies.", publisher = "IICM", journal = "Journal of Universal Computer Science", title = "All-Pairs Shortest Paths Algorithm for Regular 2D Mesh Topologies", pages = "1455-1437", number = "11", volume = "22", url = "https://hdl.handle.net/21.15107/rcub_machinery_2355" }
Cirić, V., Cvetković, A., Milentijević, I.,& Vojinović, O.. (2016). All-Pairs Shortest Paths Algorithm for Regular 2D Mesh Topologies. in Journal of Universal Computer Science IICM., 22(11), 1437-1455. https://hdl.handle.net/21.15107/rcub_machinery_2355
Cirić V, Cvetković A, Milentijević I, Vojinović O. All-Pairs Shortest Paths Algorithm for Regular 2D Mesh Topologies. in Journal of Universal Computer Science. 2016;22(11):1437-1455. https://hdl.handle.net/21.15107/rcub_machinery_2355 .
Cirić, Vladimir, Cvetković, Aleksandar, Milentijević, Ivan, Vojinović, Oliver, "All-Pairs Shortest Paths Algorithm for Regular 2D Mesh Topologies" in Journal of Universal Computer Science, 22, no. 11 (2016):1437-1455, https://hdl.handle.net/21.15107/rcub_machinery_2355 .