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

נתון גרף מכוון $G=(V,E)$ עם קדקוד מוצא $s\in V$ ויעד $t\in V$, $s\ne t$, ועם משקלים $w(e)\ne 0$ על הצלעות. בגרף ישנן $\Theta(|V|^2)$ צלעות במשקל שלילי, וגם $\Theta(|V|^2)$ צלעות במשקל חיובי. מסלול $P:s\rightsquigarrow t$ ב-$G$ ייקרא **"חוקי"** אם יש בו צלע שלילית אחת ויחידה. (מותר למסלול חוקי לעבור פעמיים דרך אותה צלע חיובית, אבל אסור לו לעבור פעמיים דרך הצלע השלילית.) הציגו אלגוריתם יעיל למציאת מסלול חוקי שמשקלו מזערי. לא יינתן שום ניקוד לאלגוריתם שזמן הריצה שלו הינו $\Theta(|V|^{2+c})$ ומעלה ($c$ מציין כאן קבוע חיובי).

רמז: מסלול חוקי = חלק חיובי מ-$s$ ל-$u$, צלע שלילית $(u,v)$, חלק חיובי מ-$v$ ל-$t$. חשבו מרחקי דייקסטרה על תת-הגרף החיובי בלבד ($d^{+}(s,\cdot)$ ו-$d^{+}(\cdot,t)$), ומזערו $d^{+}(s,u)+w(u,v)+d^{+}(v,t)$ על כל צלע שלילית.

פתרון: **רעיון:** מסלול חוקי הוא בהכרח מהצורה $s\ \xrightarrow{\text{צלעות חיוביות}}\ u\ \xrightarrow{\ (u,v)\,<0\ }\ v\ \xrightarrow{\text{צלעות חיוביות}}\ t$ — קטע ראשון וקטע אחרון המורכבים מצלעות חיוביות בלבד, והצלע השלילית היחידה $(u,v)$ ביניהם. **האלגוריתם:** 1. בנה את תת-הגרף $G^{+}$ המכיל **רק את הצלעות החיוביות** של $G$ (הסר את כל הצלעות השליליות). 2. הרֵץ דייקסטרה על $G^{+}$ מ-$s$, וקבל את המרחקים $d^{+}(s,x)$ לכל $x$. 3. הרֵץ דייקסטרה על $G^{+}$ **ההפוך** (כל הצלעות מהופכות) מ-$t$, וקבל $d^{+}(x,t)$ לכל $x$. 4. עבור כל צלע שלילית $(u,v)$ חשב $d^{+}(s,u)+w(u,v)+d^{+}(v,t)$, והחזר את המסלול בעל הערך המזערי מבין כולם. **נכונות:** דייקסטרה תקף כאן משום שב-$G^{+}$ כל המשקלים חיוביים. כל מסלול חוקי משתמש בדיוק בצלע שלילית אחת $(u,v)$; הקטעים $s\rightsquigarrow u$ ו-$v\rightsquigarrow t$ שלו מורכבים רק מצלעות חיוביות, והמשקל המזערי שלהם הוא $d^{+}(s,u)$ ו-$d^{+}(v,t)$ (עם משקלים חיוביים אין תועלת בחזרה על קדקוד, ודייקסטרה מחזיר את המינימום). מזעור על פני כל הבחירות של הצלע השלילית היחידה נותן את המסלול החוקי המזערי. **זמן ריצה:** שתי הרצות דייקסטרה, כל אחת $O(|E|+|V|\log|V|)=O(|V|^2)$ (שכן $|E|=\Theta(|V|^2)$), ומעבר על $\Theta(|V|^2)$ הצלעות השליליות — סה"כ $\Theta(|V|^2)$. $\blacksquare$