A Comparative Analysis for Shortest path Algorithms Dijkstras & Floyd-Warshall
| المؤلف الرئيسي: | Abdelrahim, Mohammed Abdelrahim Abdelrahman (Author) |
|---|---|
| مؤلفين آخرين: | Abo, Maha Abo Yousuf (Advisor) |
| التاريخ الميلادي: |
2019
|
| موقع: | الخرطوم |
| الصفحات: | 1 - 79 |
| رقم MD: | 1104309 |
| نوع المحتوى: | رسائل جامعية |
| اللغة: | الإنجليزية |
| الدرجة العلمية: | رسالة ماجستير |
| الجامعة: | جامعة النيلين |
| الكلية: | كلية علوم الحاسوب وتقانة المعلومات |
| الدولة: | السودان |
| قواعد المعلومات: | Dissertations |
| مواضيع: | |
| رابط المحتوى: |
عدد مرات التحميل
11
| المستخلص: |
مهمة العثور على أقصر مسار بين الكائنات في الرسم البياني أصبحت مهمة شائعة في حل العديد من المشكلات العلمية وهي مشكلة تحسين حظيت بالكثير من الاهتمام مؤخرا وتم إحراز تقدم كبير. يوجد هناك العديد من خوارزميات المسار الأقصر وتشرك جميعا في مهمة واحدة هي البحث عن المسار الأقصر ولكن تختلف في ما بينها من حيث وزمن تنفيذ العملية طريقة العمل وأدى ذلك لاختلاف الخوارزميات من حيث الكفاءة، لذا يجب عند البحث عن المسار الأقصر أن نتعرف على الخوارزمية الأعلى كفاءة حتى نقوم باختيارها. يهدف هذا البحث إلى المقارنة بين خوارزميتي المسار الأقصر دايكسترا وفلويد وأرشال، للتعرف على كيفية عملها ومهامهما ومزاياهما ومساوئهما لتحديد أيهما الأفضل وكيفية الاختيار بينها بالإضافة إلى تسليط الضوء على خوارزميات المسار الأقصر بشكل عام. تم استخدام المنهج الوصفي التحليلي كطريقة علمية في هذا البحث وأداة الملاحظة من خلال نتائج البرنامج المنفذ عبر لغة جافا للعثور على المسار الأقصر عن طريق خوارزميتي دايكسترا وفلويد وارشال، وتم ذلك عن طريق تصميم برنامج بلغة البرمجة جافا للبحث عن المسار الأقصر عبر خوارزميتي (دايكسترا وفلويد وارشال) ويقوم بحساب زمن التنفيذ لكليهما. توصل الباحث لنتائج أهمها أن زمن التنفيذ لخوارزمية دايكسترا عند البحث عن المسار الأقصر أقل من زمن التنفيذ لخوارزمية فلويد وارشال، خوارزمية دايكسترا لا يمكنها التعامل مع الحواف السلبية، خوارزمية فلويد وارشال أكثر فاعلية في حال كان المخطط البياني صغيرا، خوارزمية فلويد وارشال أكثر فاعلية عند البحث عن أقصر مسار لجميع العقد في المخطط البياني، كذلك توصل الباحث إلى توصيات أهمها استخدام خوارزمية دايكسترا في المخططات البيانية الكبيرة والمتوسطة بينما يجب استخدام خوارزمية فلويد وارشال في المخططات البيانية الصغيرة، يجب استخدام خوارزمية دايكسترا في المخططات البيانية المتباعدة ذات الحواف الموزونة لأنها تعمل بشكل أسرع من خوارزمية فلويد وارشال، أما بالنسبة إلى المخططات البيانية الأخرى أوصي باستخدام خوارزمية فلويد وارشال لأن خوارزمية دايكسترا قد تفشل هنالك، يجب أن لا نستخدم خوارزمية دايكسترا في الدورات السالبة، يجب استخدام خوارزمية فلويد وارشال حالة البحث عن أقصر مسار لجميع العقد في المخطط البياني. |
|---|
عناصر مشابهة
-
تحسين أداء خوارزمية ديكسرتا "Dijkstra" بتقليل زمن التوجيه
بواسطة: خلف الله، أميمة محمود فقير منشور: (2019) -
A STUDY AND IMPLEMENTATION OF SOME VISIBILITY GRAPH ALGORITHMS
بواسطة: Al Anzi, Zeyad M. منشور: (1994) -
Parallel algorithms for geometric shortest path problems
بواسطة: Phipps, Alistair K. منشور: (2004) -
A New Color Images Extraction Features Approach Based on Histogram
بواسطة: الخوالدة، شروق عاطف توفيق منشور: (2019) -
Comparative Analysis of the Performance for Cloud Computing Hypervisors with Encrypted Algorithms
بواسطة: Abd Alraheem, Waleed Khaled Amin منشور: (2014)
