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

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

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

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

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

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

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


התרשים הבא מראה זאת.

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

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

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

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

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



משפט:

מחיר המסלול הקביל הזול ביותר מ ל בגרף המקורי, קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ ל ב בגרף החדש.



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

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


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

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