شارك
الرئيسيةما هي خوارزمية ديكسترا؟
خوارزمية ديكسترا (Dijkstra Algorithm): خوارزمية بحث تتبع أسلوب الخوارزميات الجشعة، للعثور على أقصر المسارات في حالات مختلفة، إما بين العقد في الرسوم البيانية، أو للعثور على أقصر مسار لعقدة مركزية مع جميع العقد الأخرى، كما يمكن استخدامها للعثور على أقصر المسارات من عقدة واحدة إلى عقدة وجهة واحدة عن طريق إيقاف الخوارزمية بمجرد تحديد أقصر مسار إلى عقدة الوجهة.
تم تصميم خوارزمية ديكسترا من قبل عالم الحاسوب الهولندي “ادسجر ديكسترا” (Edsger W. Dijkstra) في عام 1956 وتم نشرها في عام 1959.
آلية عمل خوارزمية ديكسترا
تنتج خوارزمية ديكسترا شجرة المسار الأقصر بدءاً من المصدر المُعطى كجذر لهذه الشجرة، ثم تتابع الخوارزمية في عملها مجموعتين، الأولى تحتوي على العقد الموجودة في شجرة المسار الأقصر، والثانية تحتوي على العقد التي لم تضف بعد إلى شجرة المسار الأقصر. وتبحث الخوارزمية في كل خطوة عن العقدة الموجود في مجموعة العقد غير المضافة إلى الشجرة والتي تمتلك أقصر مسافة ممكنة عن المصدر حتى يتم المرور على كافة العقد الموجودة.
تطبيقات خوارزمية ديكسترا
من التطبيقات المستخدمة على نطاق واسع لخوارزمية ديكسترا هي بروتوكولات توجيه الشبكة لفتح مسارات الشبكة الأقصر أولاً، كما تم استخدام خوارزمية ديكسترا لاكتشاف المسارات على الطرق واختيار أقصرها على الخرائط في تطبيق “غوغل مابس” (Google Maps).
اقرأ أيضاً: