دانلود مقاله ISI انگلیسی شماره 79084
عنوان فارسی مقاله

یک الگوریتم سریع تر برای یافتن کوتاهترین مسیرمنبع مسئله تنها با چند طول مثبت و متمایز.

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79084 2010 10 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A faster algorithm for the single source shortest path problem with few distinct positive lengths
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Discrete Algorithms, Volume 8, Issue 2, June 2010, Pages 189–198

کلمات کلیدی
یافتن کوتاهترین مسیرمسئله ؛ الگوریتم تولید؛ زمان خطی؛ نمودار قرمز-آبی
پیش نمایش مقاله
پیش نمایش مقاله  یک الگوریتم سریع تر برای  یافتن کوتاهترین مسیرمنبع مسئله تنها با چند طول مثبت و متمایز.

چکیده انگلیسی

In this paper, we propose an efficient method for implementing Dijkstra's algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge lengths. The SSSPP is one of the most widely studied problems in theoretical computer science and operations research. On a graph with n vertices, m edges and K   distinct edge lengths, our algorithm runs in O(m)O(m) time if nK⩽2mnK⩽2m, and O(mlognKm) time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.