האלגוריתם של דייקסטרה, פותר
את הבעיה של מסלולים קצרים ביותר ממקור יחידעבור גרף מכוון
וממושקל, עבור משקולות אי שליליים בלבד.
עבור משקולות העשויים להיות שליליים, נשתמש באלגוריתם בלמן-פורד.
האלגוריתם מנהל קבוצה
של קודקודים שעבורם כבר נקבע סופית המסלול הקצר ביותר מן
המקור.
בכל איטרציה בוחר האלגוריתם קודקוד שעדיין אינו בקבוצה,
בעל האומדן של המסלול הקצר המינימלי מבין כל הקודקודים אשר
אינם בקבוצה, את הקודקוד הזה יכנס לתוך הקבוצה, ותתבצע הקלה
על כל הקשתות היוצאות ממנו.
במימוש האלגוריתם שנציג, אנו
מניחים כי הגרף מיוצג ע"י רשימת סמיכויות, וכדי לנהל
את כל הקודקודים שאינם בקבוצה, נשתמש בתור
קדימויות כאשר ערכי האמודנים של כל קודקוד משמשים כמפתחות.
פסאודו קוד
1. INITIALIZE-ESTIMATES
(G,s)
2. S = NULL
3. for each vertex v in G
4. ___Enqueue(Q,v)
5. while Q not empty
6. ___u = Extract-Min(Q)
7. ___S = S U {u} _________//
unite S with the vertex u
8. ___for each vertex v neighbor
of u
9. ______Improve
(u,v)
הסבר :
תחילה מתבצע איתחול, איתחול לערכי האומדן, לקבוצה ולתור
קדימויות - כך שיכיל את כל קודקודי הגרף (שורות 1-4).
כל עוד יש קודקודים בתור , כלומר קודקודים שעוד לא בקבוצה,
נוציא את הקודקוד בעל האומדן המינימלי מהתור (שורה 6) נוסיף
אותו לקבוצה (שורה 7) ומתבצעת הקלה על כל שכניו (שורות 8-9).
דוגמת הרצה
ניתוח סיבוכיות
עד כמה מהיר הוא אלגוריתם דייקסטרה
?
התשובה, תלויה במבנה הנתונים שבו נשתמש כדי לייצג את תור
הקדימויות. אם נממש את התור באמצעות מערך לינארי, כל פעולת
Extract-Min תתבצע בזמן (O(V, ומכיוון שמתבצעות V פעולות
כאלה, הזמן הכולל שהן יצרכו יהיה (O(V².
כל קודקוד מוכנס לקבוצה בידיוק פעם אחת, כך שכל קשת ברשימת
הסמיכויות של כל קודקוד נבחנת פעם אחת בלבד. סך הקשתות בכל
הרשימות הוא E, לכן מתבצעות סה"כ E איטרציות של הקלה,
שכל הקלה לוקחת (O(1.
זמן הריצה הכולל במקרה של מערך לינארי יהיה איפוא O(V²+E)
= O(V²)x.
במידה והגרף הוא דליל,
כדאי לממש את התור באמצעות ערימה
בינארית. במקרה זה, כל פעולת Extract-Min מתבצעת ב (O(logV.
כמו במקרה הקודם מתבצעות V פעולות כאלה.
הפעם, ההשמה המתבצעת בשגרה Improve, מתבצעת בזמן (O(logV,
ועדיין מתבצעות E איטרציות כאלה.
זמן הריצה הכולל במקרה של ערימה בינארית הוא איפוא O(VlogV+ElogV)
= O((V+E)logV) = O(ElogV)x.
