کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6884638 | 1444339 | 2018 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
FB-APSP: A new efficient algorithm for computing all-pairs shortest-paths
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We describe a new forward-backward method for an all-pairs shortest-paths (APSP) algorithm. While most APSP algorithms only scan edges forward, the algorithm proposed here also scans all edges backward because it assumes that edges in the outgoing and incoming adjacency lists of the vertices appear with the same importance. The running time of the algorithm on a directed graph with n vertices, and m edges and positive real-valued edge weights in a deterministic way is O(nδ2â2logδ(nâ1)â1â), and the space complexity is O(nδâ2logδ(nâ1)â1â), where δâ¯=â¯mân is the density of the graph. Simulations on graphs with up to 10000 vertices with real, positive weights show that our FB-APSP algorithm, using additional working space less than 75% of space used by Speed-Up Floyd-Warshall algorithm, is faster on large sparse graphs, particularly planar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Network and Computer Applications - Volume 121, 1 November 2018, Pages 33-43
Journal: Journal of Network and Computer Applications - Volume 121, 1 November 2018, Pages 33-43
نویسندگان
Dyson Pereira Junior, Emilio Carlos Gomes Wille,