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

נתון גרף מכוון $G=(V,E)$ עם משקלים $w(e)>0$ וקדקוד מקור $s$. בנוסף נתון עץ פורש מכוון $T$ המושרש ב-$s$. הציגו אלגוריתם המכריע האם $T$ הוא אכן עץ מסלולים מזעריים (**עמ"מ**) מ-$s$. האלגוריתם חייב לרוץ **מהר יותר אסימפטוטית** מ-Dijkstra, ופלטו הוא "כן (Accept)" או "לא (Reject)" בלבד (אינכם נדרשים לחשב עמ"מ בעצמכם).

רמז: $T$ הוא עמ"מ אם ורק אם מרחקי-העץ מקיימים את תנאי האופטימליות של Bellman: אף צלע $(u,v)$ אינה מקיימת $d(u)+w(e)<d(v)$. מעבר יחיד על הצלעות מספיק — ללא תור-קדימויות.

פתרון: **האלגוריתם.** 1. עבור מ-$s$ על העץ $T$ וחשב לכל קדקוד $u$ את $d(u)$ = משקל המסלול מ-$s$ ל-$u$ **בתוך $T$** (מעבר יחיד, $O(|V|)$). 2. לכל צלע $e=(u,v)\in E$: אם $d(u)+w(e) < d(v)$ — פלוט "לא (Reject)" וסיים. 3. פלוט "כן (Accept)". כלומר $T$ הוא עמ"מ **אם ורק אם** אף צלע אינה "מרפה" (relax) מרחק בעץ: $\;d(u)+w(u,v)\ge d(v)$ לכל צלע. **זמן ריצה.** $O(|V|)$ לחישוב $d$, ו-$O(|E|)$ למעבר על הצלעות — סה"כ $O(|V|+|E|)=O(|E|)$. מהיר יותר מ-Dijkstra ($O(|E|+|V|\log|V|)$) — ללא גורם לוגריתמי ותור-קדימויות. **הוכחת נכונות.** - **אם $T$ עמ"מ:** אז $d(u)=\delta(s,u)$ לכל $u$, ולכל צלע $(u,v)$ מתקיים אי-שוויון המשולש $\delta(s,v)\le\delta(s,u)+w(e)$, כלומר $d(u)+w(e)\ge d(v)$ — אין הפרה, ומוחזר Accept. - **אם $T$ אינו עמ"מ:** קיים קדקוד $v$ שמרחקו בעץ $d(v)$ גדול מהמרחק האמיתי. יהי $P:s\to\cdots\to v$ מסלול מזערי אמיתי; קיימת עליו צלע $e=(u,v')$ שעבורה $d(u)+w(e)<d(v')$ (אחרת כל מרחקי העץ היו אופטימליים), והאלגוריתם מזהה אותה ומחזיר Reject. $\blacksquare$