تصميم خوارزمية بزمن خطي لإيجاد المسار الاقصر في البيان
نشر في جامعة البعث
بتاريخ 2014
في مجال
والبحث باللغة
العربية
تحميل البحث
الملخص بالعربية
نقدم في هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع, و ذلك باختيار المسار بين المنبع و المسافة التي تعطي طول المسار الأقل وصولا إلى المصب. تعتمد هذه الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر, حيث يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتنا بأن زمن تنفيذ الخوارزمية المقترحة في هذا البحث هو زمن خطي قدره (O(n+L و هو يعتبر أفضل أزمنة الخوارزميات على الإطلاق.
المراجع المستخدمة
A. Kolokolova " Bellman-Ford algorithm" Applied Algorithms February 14, 2012
Chandy. K. M and Misra. J " Distributed Computation on Graphs: Shortest Path Algorithms" Communications of the ACM , Volume 25, Number I 1, November 1982
(Dijkstra. . W, "A note on two problems in connexion with graphs", Numer Math 1, 269–271. (1959