Question

shortest_path

נתון גרף מכוון G=(V,E)G = (V, E) וצומת sVs \in V ושתי פונקציות משקל w1,w2:ERw_1,w_2: E \to \mathbb{R}. ידוע שאין בגרף מעגלים שליליים לפי שתי הפונקציות הנתונות.

הציעו אלגוריתם אשר מוצא לכל vVv \in V מסלול קל ביותר מ-ss ל-vv ביחס ל-w2w_2, מבין כל המסלולים הקלים ביותר מ-ss ל-vv ביחס ל-w1w_1. על האלגוריתם לרוץ בסיבוכיות O(VE)O(VE).

1

Answers

בדומה לשאלה הזאת, נסתכל על גרף "המסלולים הקלים ביותר" ביחס ל-w1w_1.

D=(V,A)D = (V, A)

כאשר

A={uvE:d(v)=d(u)+w1(uv)}A = \{uv \in E : d(v) = d(u) + w_1(uv)\}

טענה: מסלול, s,v1,,vks, v_1, \ldots, v_k הוא מסלול קל ביותר ב-GG ביחס ל-w1w_1 אמ"מ הוא מסלול ב-DD.

הוכחה: אם המסלול s,v1,,vks, v_1, \ldots, v_k הוא מסלול קל ביותר אז מתקיים ש-d(vi)=d(vi1)+w(vi1vi)d(v_i) = d(v_{i - 1}) + w(v_{i - 1}v_{i}) לכל ii ולכן vi1viAv_{i - 1}v_{i} \in A.

מצד שני אם

s,v1,,vks, v_1, \ldots, v_k

מסלול ב-DD אז באינדוקציה על אורך המסלול מתקיים ש-s,v1,,vk1s, v_1, \ldots, v_{k - 1} מסלול קל ביותר ב-GG ובנוסף מתקיים ש-d(vk)=d(vk1+w(vk1vk))d(v_k) = d(v_{k - 1} + w(v_{k - 1}v_k)) ולכןs,v1,,vks, v_1, \ldots, v_k מסלול קל ביותר ב-GG.

כעת ניתן למצוא מסלול קל ביותר ביחס ל-w2w_2. מסלול כזה הוא המסלול המבוקש בגלל הטענה לעיל.

סיבוכיות:

  • כדי לבנות את DD צריך למצוא עץ מרחקים קלים ביותר ב-GG, אפשר לעשות זאת בזמןO(VE)O(VE) על ידי אלגוריתם בלמן-פורד.
  • מציאת מסלול קל ביותר ב-DD אפשר לעשות באותו זמן.

סך הכל O(VE)O(VE).

1
Feedback