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

נתון גרף מכוון $G=(V,E)$ עם משקלים אי-שליליים $c(e)\ge 0$ על הצלעות, וקדקוד מוצא $r\in V$. הביטו באלגוריתם הבא: **(i)** מאתחלים מערך $A$: $A[r]=0$ ו-$A[v]=\infty$ לכל $v\ne r$. **(ii)** לולאה חיצונית: חוזרים שוב ושוב על הפעולה הבאה: > **(ii.1)** לולאה פנימית: סורקים את הצלעות בסדר לקסיקוגרפי; לכל $e=(u,v)\in E$ מבצעים: אם $A[v]>A[u]+c(e)$ אז מעדכנים $A[v]\leftarrow A[u]+c(e)$. > **(ii.2)** אם בהרצה הנוכחית של כל הלולאה הפנימית לא בוצע אף עדכון — האלגוריתם מסתיים. **(א)** מה האלגוריתם מחשב? (אין צורך להוכיח.) **(ב)** יהי $B(n)$ המספר המרבי של איטרציות של הלולאה החיצונית על גרפים בעלי $n$ קדקודים. חשבו את $B(n)$, והציגו סדרת גרפים $G_n$ שעליהם מתבצעות בדיוק $B(n)$ איטרציות. **(ג)** הציגו סדרת גרפים אחרת $G'_n$ שעבורם נכנסים ללולאה החיצונית פעמיים בלבד, וזאת למרות שמספר הצלעות שלהם זהה לגרפים מסעיף (ב), כלומר $|E(G'_n)|=|E(G_n)|$.

רמז: (א) זהו בלמן-פורד — מסלולים מזעריים מ-$r$. (ב) שרשרת $v_1\to\cdots\to v_n$ עם סדר סריקה הפוך מאלץ התקדמות של צומת אחד בכל מעבר, לכן $B(n)=n$. (ג) כוכב במרכז $r$ עם $n-1$ צלעות: הכול מתעדכן במעבר אחד, ולכן $2$ איטרציות.

פתרון: **(א)** זהו אלגוריתם **בלמן-פורד**. בסיום, $A[v]$ = משקל המסלול המזערי (הקל ביותר) מ-$r$ ל-$v$, ו-$A[v]=\infty$ אם $v$ אינו ניתן להשגה מ-$r$. **(ב)** $B(n)=n$. הלולאה החיצונית מבצעת לכל היותר $n$ איטרציות ($n-1$ מעברים עד התכנסות, ועוד מעבר אחד לזיהוי שאין עדכון). כדי להגיע בדיוק ל-$n$, ניקח את **גרף-השרשרת** $G_n$: מסלול מכוון $v_1\to v_2\to\cdots\to v_n$, כל צלע במשקל $1$, עם $r=v_1$, כאשר שמות הקדקודים נבחרים כך שהסדר הלקסיקוגרפי סורק את הצלעות **מהסוף להתחלה** (הצלע $(v_{n-1},v_n)$ נסרקת ראשונה, $(v_1,v_2)$ אחרונה). אז כל איטרציה חיצונית מקבעת בדיוק קדקוד אחד נוסף: איטרציה 1 מעדכנת את $A[v_2]$, איטרציה 2 את $A[v_3]$, ..., איטרציה $n-1$ את $A[v_n]$, ואיטרציה $n$ לא מבצעת אף עדכון ועוצרת — סה"כ בדיוק $n$ איטרציות. **(ג)** ניקח את **גרף-הכוכב** $G'_n$: מרכז $r=v_1$ עם צלעות מכוונות $v_1\to v_i$ לכל $2\le i\le n$, כל אחת במשקל $1$. מספר הצלעות הוא $n-1$ — זהה לגרף-השרשרת מסעיף (ב). מ-$r=v_1$ כל הקדקודים מגיעים במרחק צלע אחת, ולכן איטרציה 1 מעדכנת את כולם, ואיטרציה 2 כבר לא מבצעת אף עדכון ועוצרת — בדיוק $2$ איטרציות. $\blacksquare$