אלגוריתם דייקסטרה
ויקיפדיה האנציקלופדיה encyclopedia
אלגוריתם דייקסטרה, פרי יצירתו של אדסחר דייקסטרה[1], הוא אלגוריתם למציאת המסלול הקל ביותר (כלומר שסכום משקלות קשתותיו הוא המינימלי האפשרי) מקדקוד (צומת) מקור לקדקוד יעד בגרף ממושקל, או למציאת כל המסלולים הקלים ביותר בגרף מקודקוד מקור לשאר הקודקודים. לכן הוא נקרא לעיתים אלגוריתם למציאת המסלולים הקלים ממקור יחיד.
עובדות מהירות סיבוכיות זמן, ממציא ...
אנימציה להמחשת האלגוריתם | |
סיבוכיות זמן | O(|E|+|V|\log |V|) |
---|---|
ממציא | אדסחר דייקסטרה |
נקרא על שם | אדסחר דייקסטרה |
הומצא | 1959 |
סגירה
האלגוריתם עובד על גרף מכוון או לא מכוון, בעל משקולות אי-שליליות על הקשתות. המשקולות בגרף מסמלות מרחק. משמעותו של המסלול הקצר ביותר בין שתי נקודות היא המסלול בעל סכום המשקולות הנמוך ביותר בין שתי הנקודות.
תוצאת האלגוריתם של דייקסטרה זהה לתוצאת אלגוריתם בלמן-פורד אך אלגוריתם בלמן-פורד פועל גם על גרפים הכוללים קשתות שמשקלן שלילי. לעומת זאת, זמן הריצה של אלגוריתם דייקסטרה מהיר יותר.