ترغب بنشر مسار تعليمي؟ اضغط هنا

مسألة المسار الأقصر لجميع العقد في البيان هي , بلا شك , واحدة من أكثر المسائل الأساسية في خوارزميات نظرية البيان . نقدم في هذا البحث خوارزمية بسيطة و فعالة من أجل مسألة المسارات الأقصر في بيان موجه ( أو غير موجه ) . في هذه المسألة نقوم بإيجاد المسار الأقصر من عقدة منبع معطاة إلى جميع العقد الأخرى في هذا البيان و الذي يكون المسار الأقصر فيه هو المسار الذي يملك أقل كلفة ( أي مجموع أوزان الأضلاع ) . أثبتنا بأن تعقيد الخوارزمية المقترحة في هذا البحث يعتمد فقط على أضلاع البيان , و بينا بأن زمن تنفيذها هو زمن خطي قدره (O(m , و هذا يعتبر أفضل أزمنة الخوارزميات على الإطلاق . ثم أجرينا مقارنة بين تعقيد الخوارزمية المقترحة و تعقيد الخوارزمية المقترحة هو الأفضل .
يمكن تصنيف مسألة المسار الأقصر إلى نوعين مختلفين من المسائل : مسألة المسار الأقصر وحيد (SSSP) المنبع و مسألة المسار الأقصر لجميع العقد (APSP). في هذا البحث أجرينا تحليل و مقارنة بين درجة التعقيد لأشهر خوارزميات المسار الأقصر, و تبين من النتائج التي ح صلنا عليها بأن جميع الأبحاث تحقق نجاحات ملحوظة و استثنائية في تصميم أفضل الخوارزميات من حيث زمن التنفيذ لحل خوارزميات المسار الأقصر.
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا