מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Dijkstra/תרגילים/Dijkstra עם העדפה למסלולים שארכם זוגי/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

נניח שזהו הגרף המקורי:

בעיית המסלול הזול ביותר.

נבנה גרף חדש כך.


ראשית, נקח את צמתי הגרף , ונשכפל אותם 3 פעמים, בקבוצות ,‏ , ו. לכל צומת בקבוצה , יש צומת ‏ ב,‏ וצומת ‏ ‏ ב.‏ התרשים הבא מראה זאת.

שכפול הצמתים.


כעת נוסיף גם קשתות:

  1. כל קשת בין ל (בגרף המקורי) - נמתח אותה בגרף החדש בין ב לבין הצומת המתאים ל ב.
  2. כל קשת בין ל (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל ב לבין הצומת המתאים ל ב.


התרשים הבא מראה זאת (רק חלק מהקשתות מצויירות).

הוספת הקשתות.

בנוסף נמתח עוד שני סוגי קשתות:

  1. לכל צומת ב, נמתח קשת במחיר בין ב לבין ‏ ב.
  2. לכל צומת ב, נמתח קשת במחיר בין ב לבין ‏ ב.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא .


המשפט הבא מסביר את חשיבות הגרף החדש.



משפט:

מחיר המסלול הזול ביותר מ ל בגרף המקורי (כולל הקנס, אם יש), קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ ל ב בגרף החדש.



הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ ל ב בגרף החדש, מורכב משני חלקים:

  1. מסלול זהה לחלוטין למסלול מ ל בגרף המקורי
  2. מסלול בעלות 1 ל ב, אם החלק הראשון זוגי, ומסלול בעלות , אם החלק הראשון אי-זוגי.


מש"ל.PNG


לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.