خوارزمية فعالة لإيجاد المسارات الأقصر لجميع العقد في البيان
نشر في جامعة البعث
بتاريخ 2015
في مجال
والبحث باللغة
العربية
تحميل البحث
الملخص بالعربية
مسألة المسار الأقصر لجميع العقد في البيان هي , بلا شك , واحدة من أكثر المسائل الأساسية في خوارزميات نظرية البيان . نقدم في هذا البحث خوارزمية بسيطة و فعالة من أجل مسألة المسارات الأقصر في بيان موجه ( أو غير موجه ) . في هذه المسألة نقوم بإيجاد المسار الأقصر من عقدة منبع معطاة إلى جميع العقد الأخرى في هذا البيان و الذي يكون المسار الأقصر فيه هو المسار الذي يملك أقل كلفة ( أي مجموع أوزان الأضلاع ) . أثبتنا بأن تعقيد الخوارزمية المقترحة في هذا البحث يعتمد فقط على أضلاع البيان , و بينا بأن زمن تنفيذها هو زمن خطي قدره (O(m , و هذا يعتبر أفضل أزمنة الخوارزميات على الإطلاق . ثم أجرينا مقارنة بين تعقيد الخوارزمية المقترحة و تعقيد الخوارزمية المقترحة هو الأفضل .
المراجع المستخدمة
Allulli. L, Lichodzijewski .P and Zeh. N, "A Faster Cache- Oblivious Shortest-Path Algorithm for Undirected Graphs with Bounded Edge Lengths", www.web.cs.dal.ca
BASWANA. S AND KAVITHA. T, "FASTER ALGORITHMS FOR ALL-PAIRS APPROXIMATE SHORTEST PATHS IN UNDIRECTED GRAPHs", Jornal of ACM,52(1), pp 1- 24. 2005. www.cse.iitk.ac.in
Bernstein. A, "Near Linear Time (1 + ϵ)-Approximation for Restricted Shortest Paths in Undirected Graphs", siam, 2011
Brandes. U, "A Faster Algorithm for Betweenness Centrality", Journal of Mathematical Sociology 25(2):163-177, (2001)