10.2 אלגוריתם דיאקסטרה (Dijkstra)

מבנה נתונים ואלגוריתמים

אלגוריתם דיאקסטרה (נקרא על שם המגלה שלו (E.W. Dijkstra) פותר את הבעיה של מציאת המסלול הקצר ביותר מנקודה בגרף (המקור) ליעד מסוים בגרף. מסתבר כי ניתן למצוא את המסלול הקצר ביותר ממקור כלשהו לכל נקודה בגרף באותו זמן, לכן בעיה זו נקראת לפעמים single source shortest paths - המסלולים הקצרים ביותר של מקור יחיד.

התוצאה המפתיעה כי כל המסלולים יכולים להימצא באותה קלות שניתן למצוא מסלול אחד מדגימה את החשיבות של קריאת ספרות בנושא אלגוריתמים!

בעיה זו קשורה לבעיית העץ הפורש. הגרף המייצג את כל המסלולים מקדקוד אחד לכל השאר חייב להיות עץ פורש - הוא צריך לכלול את כל הקדקודים. בנוסף, לא יהיה בו אף מעגל, מפני שמעגל קובע יותר ממסלול אחד מהקודקוד הנבחר לפחות קדקודים אחד אחר.

עבור הגרף G = (V,E), כאשר:

· V היא סדרה של קדקודים

· E היא סידרה של צלעות

האלגוריתם של דיאקסטרה שומר שתי קבוצות של קדקודים:

S - קבוצת הקדקודים שהמסלולים הקצרים ביותר שלהם מהמקור כבר נקבעו.

V-S - קבוצה המכילה את שאר הקדקודים שנותרו.

מבני הנתונים הנוספים שבהם יש צורך הם:

d - מערך של ההערכות הטובות ביותר של המסלול הקצר ביותר לכל קדקוד.

pi - מערך של הקדקודים הקדומניים (predecessors) של כל קדקוד.

המהלך הבסיסי של האלגוריתם הוא:

1. אתחול של d ושל pi.

2. קביעת S כקבוצה ריקה.

3. כל עוד ישנם קדקודים ב- S-V:

א. מיון את הקודקודים ב- S-V על פי ההערכה הנוכחית הטובה ביותר של מרחקם מהמקור.

ב. הוספת u, הקדקוד הקרוב ביותר שב- S-V, ל- S.

ג. הרפיה של כל הקדקודים אשר עדיין ב- S-V ומקושרים ל- u.

הרפיה (Relaxation)

הליך ההרפיה מעדכן את העלויות של כל הקדקודים v, המקושרים לקדקוד u, אם נשפר את ההערכה הטובה ביותר באשר למסלול הקצר ביותר ל- v על ידי הכללת (u,v) במסלול ל- v.

הליך ההרפיה נראה כך:

initialise_single_source( Graph g, Node s )

for each vertex v in Vertices( g )

g.d[v] := infinity

g.pi[v] := nil

g.d[s] := 0;

הליך זה מעדכן את הגרף כך שלאף צומת אין קדומני (pi[v] = nil), והערכות העלות (המרחק) של כל צומת מהמקור (d[v]) הן אינסופיות, מלבד ההערכה עבור צומת המקור עצמה (d[s] = 0).

שים לב כי הוצגה כאן גם דרך נוספת לאחסון הגרף (או חלק מגרף - כי מבנה זה יכול לאחסן רק עץ פורש), תת-הגרף הקדומני - רשימת הקדקודים הקודמים לכל צומת: Pi[j],1 <= j <=[v]. הצלעות של תת-הגרף הקדומני יהיו: [pi[v],v].

הליך ההרפיה בודק האם ההערכה הטובה ביותר הנוכחי של המרחק הקצר ביותר ל- v (d[v]) יכול להשתפר על ידי מעבר דרך u (כלומר על ידי הפיכת u לקדומני של v):

relax( Node u, Node v, double w[][] )

if d[v] d[u] + w[u,v] then

d[v] := d[u] + w[u,v]

pi[v] := u

האלגוריתם עצמו יהיה כעת:

shortest_paths( Graph g, Node s )

initialise_single_source( g, s )

S := { 0 } /* Make S empty */

Q := Vertices( g ) /* Put the vertices in a PQ */

while not Empty(Q)

u := ExtractCheapest( Q );

AddNode( S, u ); /* Add u to S */

for each vertex v in Adjacent( u )

relax( u, v, w )

פעולת האלגוריתם Dijkstra

כרגיל, ההוכחה של אלגוריתם חמדני הוא החלק ה"טריקי" ביותר.

אנימציה

באנימציה הבאה, מספר מקרים נבחרו על מנת להראות את כל האספקטים של פעולת אלגוריתם דיאקסטרה. התחל בבחירת מערך הנתונים (או שתוכל להשתמש באפשרות הראשונה שהיא ברירת המחדל), לאחר מכן בחר ב- step או ב- run על מנת להריץ את האלגוריתם. שים לב כי האלגוריתם מתחיל בקביעת משקל של אינסוף לכל הצמתים, ולאחר מכן בוחר מקור וקובע לו משקל של אפס.

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

אנימציה אלטרנטיבית של אלגוריתם דיאקסטרה יכולה לתת לך תובנה שונה!

מושגים

בעיית המסלולים הקצרים ביותר של מקור יחיד

שם תיאורי עבור הבעיה של מציאת המסלולים הקצרים ביותר לכל הצמתים בגרף ממקור

נבחר. בעיה זו מוכרת על ידי האלגוריתם המשמש לפתירתה - אלגוריתם דיאקסטרה.

רשימה קדומנית

מבנה עבור אחסון מסלול העובר דרך גרף.

המשך ל: פעולת אלגוריתם דיאקסטרה המשך ל: קידוד הופמן חזור ל: תוכן עניינים