שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2026 - גרפים

שאלה 4 (10 קודקודים): נתון שדרך בעיית מסלול קצר בין שני צמתים בגרף, בעזרת אלגוריתם של דייקסטרה. עבור צמת התחלה $s = 0$, חשב את המרחקים הקצרים ביותר מן ה־$s$ לכל שאר הצמתים, תוך שימוש בטבלה המתעדכנת בכל איטרציה.

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

פתרון: כדי למצוא את המסלולים הקצרים ביותר מצומת המקור $s=0$ לכל שאר הצמתים בגרף, נשתמש ב**אלגוריתם דייקסטרה**. האלגוריתם מתחזק קבוצה $S$ של צמתים שהמרחק הסופי אליהם כבר ידוע, ומערך מרחקים $d$ המכיל את אומדן המרחק הקצר ביותר מ-$s$ לכל צומת. **אתחול:** - קובעים את המרחק לצומת המקור ל-0: $d[0] = 0$. - קובעים את המרחק לכל שאר הצמתים לאינסוף: $d[v] = \infty$ עבור $v \neq 0$. - קבוצת הצמתים שנסגרו, $S$, ריקה בתחילה. **איטרציות:** בכל שלב, האלגוריתם בוחר צומת $u$ שאינו ב-$S$ ובעל ערך $d[u]$ המינימלי. לאחר מכן, $u$ מתווסף ל-$S$ ומבוצעת פעולת **הרפיה (relaxation)** על כל הקשתות היוצאות מ-$u$. עבור כל שכן $v$ של $u$, אם מתקיים $d[u] + w(u,v) < d[v]$, מעדכנים את $d[v]$ לערך החדש והקטן יותר. **מעקב אחר ריצת האלגוריתם:** הטבלה הבאה מציגה את ערכי מערך המרחקים $d$ לאחר כל איטרציה. העמודה $u$ מציינת את הצומת שנבחר (הוצא מהתור) באותה איטרציה, והערך המודגש הוא מרחקו הסופי שנקבע. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{איטרציה} & u & d[0] & d[1] & d[2] & d[3] & d[4] & d[5] & d[6] & d[7] & d[8] & d[9] \\ \hline \text{אתחול} & - & 0 & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \hline 1 & 0 & \mathbf{0} & 4 & \infty & \infty & \infty & \infty & \infty & 8 & \infty & \infty \\ \hline 2 & 1 & 0 & \mathbf{4} & 12 & \infty & \infty & \infty & \infty & 8 & \infty & \infty \\ \hline 3 & 7 & 0 & 4 & 12 & \infty & \infty & \infty & \infty & \mathbf{8} & 15 & \infty \\ \hline 4 & 2 & 0 & 4 & \mathbf{12} & 19 & \infty & 16 & \infty & 8 & 14 & \infty \\ \hline 5 & 8 & 0 & 4 & 12 & 19 & \infty & 16 & \infty & 8 & \mathbf{14} & \infty \\ \hline 6 & 5 & 0 & 4 & 12 & 19 & \infty & \mathbf{16} & 18 & 8 & 14 & \infty \\ \hline 7 & 6 & 0 & 4 & 12 & 19 & \infty & 16 & \mathbf{18} & 8 & 14 & \infty \\ \hline 8 & 3 & 0 & 4 & 12 & \mathbf{19} & 28 & 16 & 18 & 8 & 14 & \infty \\ \hline 9 & 4 & 0 & 4 & 12 & 19 & \mathbf{28} & 16 & 18 & 8 & 14 & \infty \\ \hline 10 & 9 & 0 & 4 & 12 & 19 & 28 & 16 & 18 & 8 & 14 & \mathbf{\infty} \\ \hline \end{array} $$ **סיכום התוצאות:** לאחר סיום האלגוריתם, וקטור המרחקים הקצרים ביותר מצומת 0 הוא: $d = [0, 4, 12, 19, 28, 16, 18, 8, 14, \infty]$ המשמעות היא: - המרחק מ-0 ל-0 הוא 0. - המרחק מ-0 ל-1 הוא 4. - המרחק מ-0 ל-2 הוא 12. - המרחק מ-0 ל-3 הוא 19. - המרחק מ-0 ל-4 הוא 28. - המרחק מ-0 ל-5 הוא 16. - המרחק מ-0 ל-6 הוא 18. - המרחק מ-0 ל-7 הוא 8. - המרחק מ-0 ל-8 הוא 14. - אין מסלול מ-0 ל-9, ולכן המרחק הוא אינסוף. $\blacksquare$