איך מבצעים את אלגוריתם דייקסטרא (Dijkstra)

Steps

1. 1

   Step 1

   
   אז יש לנו גרף מכוון, ממושקל ומגניב המתחיל מקודקוד S. נכתוב ליד הגרף שלנו את רשימת כל הקודקודים לפני שאנחנו מריצים את דייקסטרא.
2. 2

   Step 2

   
   נאתחל את כל המשקלים על הקודקודים שלנו לאינסוף (מלבד הקודקוד S) יופי, אז אפשר להתחיל.
3. 3

   Step 3

   
   נבחר קשת היוצאת מS, כרגע לא משנה איזה, אני בחרתי במקרה בקשת בין S לb. נבדוק האם משקל הקשת קטן ממשקל הקודקוד b. אכן, 5 קטן יותר מאינסוף ולכן נחליף את משקל הקודקוד של b ל5.
4. 4

   Step 4

   
   נבחר את הקשת הבאה היוצאת מS, הקשת מS לa. נבדוק האם משקל הקשת קטן ממשקל הקודקוד a. אכן, 8 קטן יותר מאינסוף ולכן נחליף את משקל הקודקוד של a ל8.
5. 5

   Step 5

   
   לאחר שסיימנו לעבור על כל הקשתות היוצאות מS , נמחק אותו מהרשימה שלנו בכדי לדעת שעברנו עליו ושאי אפשר לגשת אליו יותר. נעבור עכשיו לקודקוד ההבא בגרף הקרוב לS ובעל המשקל הנמוך ביותר - במקרה שלנו b ונבחן את קשתותיו. נסתכל על הקשת מb לa ונבדוק האם משקל הקודקוד b + משקל הקשת בין b לa קטן ממשקל הקודקוד a. אם כן, נחליף את משקל הקודקוד a. ואכן במקרה שלנו 5+2<8 ונחליף את משקל הקודקוד a ב7
6. 6

   Step 6

   
   נעבור לקשת הבאה היוצאת מb - הקשת מb לc ונשאל את אותה שאלה: האם משקל הקודקוד b + משקל הקשת בין b לc קטן ממשקל הקודקוד c. אכן, 5+8 < אינסוף ולכן נחליף את משקל קודקוד c ב13.
7. 7

   Step 7

   
   נעבור לקשת הבאה היוצאת מb - הקשת מb לd. ונבדוק: האם משקל הקודקוד b + משקל הקשת בין b לd קטן ממשקל הקודקוד d. אכן 5+4< אינסוף ולכן נחליף את משקל קודקוד d ב9 הערה:שימו לב שכל פעם שאנחנו בוחנים את הקודקוד הבא אנו צריכים לבדוק שאינו מחוק מהרשימה שלנו.
8. 8

   Step 8

   
   עכשיו שסיימנו עם כל הקשתות היוצאות מקודקוד b, נמחק אותו מהרשימה בכדי שלא ניגש אליו שוב. יופי, כעת נבחר את הקודקוד הקרוב b ובעל המשקל הנמוך ביותר ונחזור על התהליך. הקודקוד הקרוב ביותר לb ובעל המשקל הנמוך ביותר הוא a. לא נתמקד בקשת מa לb מכיוון שb מחוק מהרשימה שלנו ונעבור ישר לקשת מa לc. נבדוק: האם משקל הקודקוד a + משקל הקשת בין a לc קטן ממשקל הקודקוד c. אכן 7+1<13 ונחליף את משקל הקודקוד של c ל8.
9. 9

   Step 9

   
   סיימנו עם a אז נמחק אותו מהרשימה ונעבור לקודקוד הבא הקרוב לa בעל המשקל הנמוך ביותר ושאינו מחוק מהרשימה - במקרה שלנו זהו קודקוד c. שימו לב מה קורה עכשיו, הקודקוד הקרוב לc שאינו מחוק מהרשימה הוא d וכפי שניתן לראות משקל הקודקוד של c + משקל הקשת בין c לd גדול ממשקל קודקוד d. לכן, פשוט לא נעשה שום דבר ונמחק את c מהרשימה.
10. 10

    Step 10

    
    נעבור לקודקוד האחרון ברשימה, קודקוד d. וגם כאן ניתן לראות שיש מבוי סתום, אין קודקודים הקרובים אליו שאינם מחוקים מהרשימה ולכן גם אותו נמחק מהרשימה. זהו, ראיתם איך אלגוריתם דייקסטרא עובד ויש בידכם את המסלול הקצר ביותר מקודקוד אחד לכל הקודקודים.