Question

shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות חיוביות על הקשתות, ויהא sVs \in V. נאמר כי קשת היא שימושית אם קיים מסלול קל ביותר מ-ss ל-vv שהקשת uvuv היא האחרונה בו. נאמר שמסלול מ-ss ל-tt הוא שני קל ביותר אם משקלו הוא הקל ביותר מבין כל המסלולים מ-ss ל-tt שמשקלם גדול ממש ממשקל המסלול הקל ביותר מ-ss ל-tt.

  1. יהא PP מסלול מ-ss ל-tt. הוכיחו כי PP מסלול קל ביותר מ-ss ל-tt אם ורק אם כל קשתות PP שימושיות.
  2. יהא PP מסלול מ-ss ל-tt. הוכיחו כי אם PP הוא שני קל ביותר אז ב-PP יש בדיוק קשת אחת שאינה שימושית.
  3. הציעו אלגוריתם, יעיל ככל שתוכלו, המוצא מסלול שני קל ביותר מ-ss ל-tt או מודיע כי לא קיים כזה.
1

Answers

1. נניח ש-PP מסלול קל ביותר מ-ss ל-tt ונניח בשלילה שקיימת בו קשת לא שימושית uvuv אז משקל המסלול הקל ביותר מ-ss ל-vv ועוד משקל המסלול הקל ביותר מ-vv ל-tt קטן ממש ממשקלו של PP - סתירה.

נניח שכל הקשתות ב-PP שימושיות ונראה באינדוקציה שלכל צומת vv במסלול תת המסלול מ-ss ל-vv הוא מסלול קל ביותר:

בסיס: עבור ss הטענה מתקיימת.

צעד: אם המסלול מ-ss ל-uu הוא קל ביותר ו-uvuv קשת שימושית אז המסלול מ-ss ל-vv הוא מסלול קל ביותר.

2. אם ב-PP כל הקשתות שימושיות אז מסעיף 1 נובע שהוא קל ביותר. נניח שיש ב-PP יותר מקשת אחת לא שימושית ונסתכל על הקשת הראשונה הלא שימושית במסלול, uvuv, אז אם נחליף את הרישא של PP מ-ss ל-vv במסלול קל ביותר מ-ss ל-vv נקבל מסלול קל יותר מ-PP אבל לפי טענה 1 הוא לא מסלול קל ביותר - סתירה.

3. האלגוריתם:

  • מצא את כל הקשתות השימושיות:
    • הרץ אלג דיקסטרה
    • בחר את כל הקשתות uvuv כך ש-d(s,v)=d(s,u)+w(uv)d(s, v) = d(s, u) + w(uv)
  • נסמן ב-FF את הקשתות הלא שימושיות, החזר את המסלול שמתאים ל-minuvFd(s,u)+w(uv)+d(v,t)\min_{uv \in F} d(s, u) + w(uv) + d(v, t).

נכונות: נובע מכך שאנחנו בודקים את כל המסלולים האפשריים שמכילים קשת לא שימושית אחת.

סיבוכיות: דיקסטרה לוקח O(ElogV)O(E \log V) ושאר הפעולות נבלעות בסיבוכיות הנ"ל.

1
Feedback