تمت عملية الاشتراك بنجاح

إغلاق

عذراً، أنت مشترك مسبقاً بالنشرة البريدية

إغلاق
facebook
twitter
whatsapp
email
linkedin
messenger

خوارزمية ديكسترا

ما هي خوارزمية ديكسترا؟ 

خوارزمية ديكسترا (Dijkstra Algorithm): خوارزمية بحث تتبع أسلوب الخوارزميات الجشعة، للعثور على أقصر المسارات في حالات مختلفة، إما بين العقد في الرسوم البيانية، أو للعثور على أقصر مسار لعقدة مركزية مع جميع العقد الأخرى، كما يمكن استخدامها للعثور على أقصر المسارات من عقدة واحدة إلى عقدة وجهة واحدة عن طريق إيقاف الخوارزمية بمجرد تحديد أقصر مسار إلى عقدة الوجهة.

إعلان: لا تدع حائط الدفع يفصلك عن أهم المهارات والخبرات الإدارية. استفد اليوم من الاشتراك الترحيبي بدءاً من 30 ريال/درهم (8 دولار).

تم تصميم خوارزمية ديكسترا من قبل عالم الحاسوب الهولندي "ادسجر ديكسترا" (Edsger W. Dijkstra) في عام 1956 وتم نشرها في عام 1959.

آلية عمل خوارزمية ديكسترا

تنتج خوارزمية ديكسترا شجرة المسار الأقصر بدءاً من المصدر المُعطى كجذر لهذه الشجرة، ثم تتابع الخوارزمية في عملها مجموعتين، الأولى تحتوي على العقد الموجودة في شجرة المسار الأقصر، والثانية تحتوي على العقد التي لم تضف بعد إلى شجرة المسار الأقصر. وتبحث الخوارزمية في كل خطوة عن العقدة الموجود في مجموعة العقد غير المضافة إلى الشجرة والتي تمتلك أقصر مسافة ممكنة عن المصدر حتى يتم المرور على كافة العقد الموجودة. 

تطبيقات خوارزمية ديكسترا

من التطبيقات المستخدمة على نطاق واسع لخوارزمية ديكسترا هي بروتوكولات توجيه الشبكة لفتح مسارات الشبكة الأقصر أولاً، كما تم استخدام خوارزمية ديكسترا لاكتشاف المسارات على الطرق واختيار أقصرها على الخرائط في تطبيق "غوغل مابس" (Google Maps).

اقرأ أيضاً:

أرسل لنا اقتراحاتك لتطوير محتوى المفاهيم

اقرأ أيضاً في هارفارد بزنس ريفيو

بدعم من تقنيات

error: المحتوى محمي !!