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

הקלט לאלגוריתם של Dijkstra הינו, כזכור, גרף $G$ עם קדקוד מוצא $s$ ועם משקלי צלעות אי-שליליים $w(e)$, והפלט הינו עץ עמ"מ (מסלולים-מזעריים) מהמוצא $s$ לכל יתר הקדקודים של הגרף הנגישים בגרף. ענו על שני הסעיפים הנפרדים הבאים (שימו לב: סעיף (ב) ממשיך בעמוד הבא). (א) (9 נק') הוכיחו בקצרה או הפריכו בקצרה את הטענה הבאה: "אם $T$ הינו עמ"מ ביחס למשקלים המקוריים, אזי $T$ הינו עמ"מ גם ביחס למשקלים החדשים, כאשר $w'(e) := k_1 \cdot w(e) + k_2$, כאשר $k_1, k_2$ הינם שני קבועים שלמים וחיוביים". (ב) בסעיף זה נבצע הרצה של אלגוריתם Dijkstra על הגרף הממושקל $G$ שמצויר להלן משמאל, כשתור-הקדימויות ממומש באמצעות ערימה-בינארית $H$ שמאותחלת מראש למצב שמצויר להלן מימין. בציור של הערימה רושמים בתוך כל קדקוד את השם שלו, ורושמים מימין לכל קדקוד את המשקל של המסלול הטוב ביותר, שחושב עבורו עד כה. תשובתכם צריכה לכלול אך ורק ציור של עץ הפלט $T$ בסיומה (3 נק'), וציורים של הערימה $H$ של כל "איטרציה" של האלגוריתם (13 נק'). כזכור, בסיומה של איטרציה $i$ העץ $T$ כולל בדיוק $i$ קדקודים (בנוסף לקדקוד המוצא $s$), ואלו הם הקדקודים עבורם חושב סופית מסלול מזערי.

רמז: חשבו כיצד הטרנספורמציה $w'(e) := k_1 \cdot w(e) + k_2$ משפיעה על משקל כולל של מסלול. האם המשקל החדש תלוי רק במשקל המקורי של המסלול, או גם בתכונה נוספת של המסלול?

פתרון: סעיף (א): הטענה אינה נכונה. נפריך אותה באמצעות דוגמה נגדית. נבחן את הגרף $G=(V,E)$ הבא: $V = \{s, a, t\}$, $E = \{(s,a), (a,t), (s,t)\}$. קדקוד המוצא הוא $s$. נגדיר את משקלי הצלעות המקוריים $w$ באופן הבא: $w(s,a) = 1$ $w(a,t) = 1$ $w(s,t) = 3$ כעת, נחשב את המסלולים הקצרים מהמוצא $s$ לקדקוד $t$: 1. המסלול $P_1 = s \to a \to t$. משקלו הוא $W(P_1) = w(s,a) + w(a,t) = 1+1=2$. 2. המסלול $P_2 = s \to t$. משקלו הוא $W(P_2) = w(s,t) = 3$. מכיוון ש-$W(P_1) < W(P_2)$, המסלול המזערי מ-$s$ ל-$t$ הוא $P_1$. לכן, ב**עץ המסלולים המזעריים** (עמ"מ) $T$ היוצא מ-$s$, הקדקוד $t$ יחובר דרך הקדקוד $a$. כלומר, הצלעות $(s,a)$ ו-$(a,t)$ יהיו חלק מ-$T$. כעת, נבחר את הקבועים החיוביים והשלמים $k_1 = 1, k_2 = 2$. נגדיר את משקלי הצלעות החדשים $w'(e) := 1 \cdot w(e) + 2 = w(e)+2$: $w'(s,a) = 1+2=3$ $w'(a,t) = 1+2=3$ $w'(s,t) = 3+2=5$ נחשב את משקלי המסלולים מ-$s$ ל-$t$ ביחס למשקלים החדשים $w'$: 1. המסלול $P_1 = s \to a \to t$. משקלו החדש הוא $W'(P_1) = w'(s,a) + w'(a,t) = 3+3=6$. 2. המסלול $P_2 = s \to t$. משקלו החדש הוא $W'(P_2) = w'(s,t) = 5$. כעת, $W'(P_2) < W'(P_1)$. לכן, תחת המשקלים החדשים $w'$, המסלול המזערי מ-$s$ ל-$t$ הוא $P_2$. בעץ המסלולים המזעריים החדש $T'$, הקדקוד $t$ יהיה מחובר ישירות ל-$s$ באמצעות הצלע $(s,t)$. מכיוון שהעץ המקורי $T$ והעץ החדש $T'$ שונים (המסלול מ-$s$ ל-$t$ השתנה), הראינו שטענה אינה נכונה. העץ $T$ שהיה עמ"מ עבור $w$ אינו עמ"מ עבור $w'$. הסיבה לכך היא שמשקלו החדש של מסלול $P$ המורכב מ-$m$ צלעות הוא $W'(P) = \sum_{e \in P} (k_1 w(e) + k_2) = k_1 W(P) + m \cdot k_2$. הטרנספורמציה אינה שומרת על סדר אורכי המסלולים, מכיוון שהיא מוסיפה "קנס" התלוי במספר הצלעות במסלול, ולא רק במשקלו המקורי. $\blacksquare$ סעיף (ב): לא ניתן לענות על סעיף זה מכיוון שהגרף $G$ והמצב ההתחלתי של הערימה $H$ הנדרשים לביצוע ההרצה חסרים בטקסט השאלה.