שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2020 - מסלולים קצרים

נזכיר את בעיית המסלולים המזעריים ממקור יחיד: נתון גרף מכוון $G=(V,E)$ עם משקלים $w(e)>0$ וקדקוד מקור $s$; מחפשים מסלולים מזעריים מ-$s$ ליתר הקדקודים. נניח לשם פשטות שאין ב-$G$ שני קדקודים שונים בעלי **אותו מרחק** מהמקור. יהי $T$ העץ ש-Dijkstra מתחזק במהלך ריצתו. הוכיחו באינדוקציה את הטענה: > בכל איטרציה $i$ של Dijkstra יש מספר ממשי $d_i$, כך שהעץ $T$ פורש בסיום אותה איטרציה בדיוק את כל הקדקודים שמרחקם מהמקור ב-$G$ הוא לכל היותר $d_i$.

רמז: $d_i$ הוא פשוט מרחקו של הקדקוד האחרון שנוסף לעץ. נצלו את העובדה ש-Dijkstra מוסיף קדקודים בסדר מרחק לא-יורד מ-$s$.

פתרון: נוכיח באינדוקציה על $i$ (מספר האיטרציה). **בסיס ($i=1$).** בסיום האיטרציה הראשונה $T$ פורש את $s$ ואת הקדקוד הקרוב אליו ביותר. נבחר $d_1$ = המרחק המזערי מ-$s$ (המרחק לקדקוד הקרוב). אז $T$ פורש בדיוק את הקדקודים שמרחקם $\le d_1$ (בהנחת ייחוד המרחקים, רק $s$ ושכנו הקרוב). **הנחה.** נניח שבסיום איטרציה $i$ קיים $d_i$ כך ש-$T$ פורש בדיוק את הקדקודים שמרחקם מ-$s$ הוא $\le d_i$. **צעד.** אם באיטרציה $i{+}1$ האלגוריתם הסתיים, $T$ לא השתנה ו-$d_{i+1}=d_i$. אחרת נוסף קדקוד חדש $v$, שהוא בעל $d$-הערך המזערי ב-$V\setminus T$ (בחירת Dijkstra). נסמן $d_{i+1}=\text{dist}(s,v)$. מכיוון ש-Dijkstra מוסיף קדקודים בסדר מרחק **לא-יורד**: - לכל $u\in T$ (כולל אלו מהאיטרציות הקודמות ו-$v$) מתקיים $\text{dist}(s,u)\le d_{i+1}$; - לכל $u\notin T$ מתקיים $\text{dist}(s,u) > d_{i+1}$ (אחרת היה נבחר במקום $v$). לכן $T$ פורש בסיום איטרציה $i{+}1$ בדיוק את הקדקודים שמרחקם $\le d_{i+1}$. $\blacksquare$