10.2.1 פעולת אלגוריתם דיאקסטרה
מבנה
נתונים ואלגוריתמים
רצף דיאגרמות
זה מדגים את פעולת אלגוריתם דיאקסטרה.
1. הגרף בהתחלה - כל הצמתים בעלי ערכי מרחק
אינסופיים מלבד המקור.
2. א. בחר את הצומת
הקרובה ביותר ל- s.
ב. הוסף אותה ל- S.
ג. הרפה את כל הצמתים השכנים
של s.
ד.עדכן את הקדומניים (החצים
האדומים) עבור כל הצמתים המעודכנים.
3. א. בחר את
הצומת הקרוב ביותר - x.
ב. הרפה את כל הצמתים השכנים
של .x
ג. עדכן את הקודמים עבור u, v ו- y.
4. א. כעת y הוא הקרוב ביותר, הוסף אותו ל- S.
ב. הרפה את v
ועדכן את הקדומני שלו.
5. u הוא כעת הקרוב ביותר, בחר אותו והתאם את השכן שלו v.
6. לבסוף, הוסף
את v. הרשימה הקדומניים מגדירה
כעת את הנתיב הקצר ביותר מכל צומת ל- s.
חזור ל: אלגוריתם דיאקסטרה חזור
ל: תוכן עניינים