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

שאלה 4 – מסלולים קצרים בגרפים (עמוד 12) נתון גרף קשיר ולא מכוונן $G = (V, E)$ עם משקלות על הקשתות (אם קיימים). נניח שהגרף לא מכיל מעגלים שליליים. מטרה: כתבו את הדרוג $G'$ בתוך הדרוג הנתון, כאשר $G'$ היא תת-גרף קשיר המכיל: 1. חדרות הרודג $G'$ 2. יחודות חציבה בין $G$ לפי $G'$ 3. יחודות קשירות בין $G$ לפי $G'$ 4. מה הגלוריתמים מבצעים עם $G'$ בנסיגה לסדור? 5. הוכחות קשירות בין $G$ לפי $G'$ 6. וכמה אלגוריתמים משתמשים במטריצות הסמיכות לחישוב מסלולים קצרים? 7. מה הגלוריתמים מבצעים עם $G'$ ומדוע זה סופיסטי?

רמז: ניתן לפרש את $G'$ המבוקש כעץ המסלולים הקצרים ביותר (SPT) מצומת מקור כלשהו $s$. חישבו כיצד אלגוריתמים כמו דייקסטרה בונים ומנצלים מבנה זה.

פתרון: השאלה, כפי שהיא מנוסחת, אינה ברורה ומשתמשת בטרמינולוגיה לא סטנדרטית. נפרש את השאלה מתוך ההקשר של מסלולים קצרים בגרפים, ונניח כי $G'=(V', E')$ הוא **עץ המסלולים הקצרים ביותר** (Shortest Path Tree - SPT) מנקודת מקור $s$ בגרף $G$. עץ זה הוא תת-גרף של $G$ המקיים שני תנאים: (1) הוא עץ מושרש ב-$s$. (2) עבור כל צומת $v otin V'$, המסלול היחיד מ-$s$ ל-$v$ בעץ $G'$ הוא גם מסלול קצר ביותר מ-$s$ ל-$v$ בגרף המקורי $G$. בהינתן פרשנות זו, נענה על הסעיפים: 1. **צמתי הגרף $G'$**: מכיוון שהגרף המקורי $G$ קשיר, קיים מסלול מ-$s$ לכל צומת אחר $v otin V$. לכן, עץ המסלולים הקצרים ביותר $G'$ יכלול את כל צמתי הגרף המקורי. כלומר, $V' = V$. 2. ו-3. **חתכים וקשירות**: אלגוריתמים לבניית עץ מסלולים קצרים, כמו **אלגוריתם דייקסטרה**, עובדים על ידי חלוקה של צמתי הגרף $V$ לשתי קבוצות: קבוצה $S$ של צמתים שהמרחק הקצר ביותר אליהם מ-$s$ כבר ידוע, וקבוצה $V-S$ של שאר הצמתים. בכל שלב, האלגוריתם בוחר צומת $u otin V-S$ בעל אומדן המרחק הקטן ביותר מ-$s$ ומוסיף אותו ל-$S$. הקשת שחיברה את $u$ לצומת שכבר היה ב-$S$ מתווספת לעץ $G'$. פעולה זו מתבססת על **תכונת החתך** (Cut Property) של מסלולים קצרים: עבור כל חתך $(S, V-S)$ של $V$ כך ש-$s otin S$, אם $e=(u,v)$ היא קשת קלה ביותר שחוצה את החתך מ-$S$ ל-$V-S$, אז קשת זו היא חלק ממסלול קצר כלשהו מ-$s$ ל-$v$. $G'$ מבטיח קשירות מ-$s$ לכל צומת אחר. 4. **פעולת האלגוריתמים**: אלגוריתמים כמו דייקסטרה ובלמן-פורד בונים את $G'$ באופן **איטרטיבי**, לא רקורסיבי. הם מתחילים עם $s$ ומרחיבים את העץ צומת אחר צומת. **אלגוריתם דייקסטרה** עושה זאת באופן חמדני על ידי בחירת הצומת הקרוב ביותר שטרם התגלה. **אלגוריתם בלמן-פורד** מבצע $V-1$ איטרציות, ובכל איטרציה עובר על כל הקשתות ומבצע פעולות **רלקסציה** (relaxation), עד שהמרחקים מתייצבים. 5. **הוכחות קשירות ונכונות**: הוכחת הנכונות של אלגוריתם דייקסטרה, לדוגמה, משתמשת ב**שמורת לולאה**: בתחילת כל איטרציה של הלולאה הראשית, לכל צומת $u otin S$, המרחק $d[u]$ המחושב הוא המרחק הקצר ביותר מ-$s$ ל-$u$ שעובר רק דרך צמתים ב-$S$. ההוכחה מתבצעת באינדוקציה על גודל הקבוצה $S$ ומראה שהבחירה החמדנית מובילה תמיד למסלול קצר אופטימלי, בהנחה שאין משקלים שליליים. בסיום, $G'$ שנוצר הוא אכן עץ קשיר המכיל את המסלולים הקצרים ביותר. $\blacksquare$ 6. **אלגוריתמים המשתמשים במטריצת שכנויות**: מספר אלגוריתמים לחישוב מסלולים קצרים מיועדים או יכולים להיות ממומשים ביעילות באמצעות מטריצת שכנויות, במיוחד עבור גרפים צפופים: * **אלגוריתם פלויד-וורשל (Floyd-Warshall)**: זהו אלגוריתם קלאסי לבעיית **כל הזוגות מסלולים קצרים** (All-Pairs Shortest Paths). הוא מבוסס על תכנות דינמי ופועל בסיבוכיות $O(|V|^3)$, המתאימה לייצוג מטריציוני. * מימוש של **אלגוריתם דייקסטרה** באמצעות מטריצת שכנויות (ללא תור עדיפויות מתוחכם): מציאת הצומת עם המרחק המינימלי בכל שלב לוקחת $O(|V|)$ זמן, מה שמוביל לסיבוכיות כוללת של $O(|V|^2)$. * **אלגוריתם בלמן-פורד**: ניתן לממשו באמצעות מעבר על מטריצת השכנויות. סיבוכיות הזמן שלו, $O(|V| \cdot |E|)$, הופכת ל-$O(|V|^3)$ בגרף צפוף, מה שמתאים לייצוג מטריציוני. 7. **תפקיד $G'$ ומורכבותו**: האלגוריתמים למעשה *בונים* את $G'$ כתוצר לוואי של חישוב המרחקים. מבנה זה הוא מתוחכם (sophisticated) מכיוון שהוא מהווה פתרון קומפקטי לבעיית ה-Single-Source Shortest Paths. במקום לשמור את כל המסלולים, אנו שומרים רק עץ, שממנו ניתן לשחזר את המסלול הקצר ביותר מ-$s$ לכל צומת אחר. היעילות והנכונות של האלגוריתמים הנדרשים לבנייתו, כמו דייקסטרה, אינן טריוויאליות ותלויות בתכונות עמוקות של הגרף (כמו אי-קיום משקלים שליליים).