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

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

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

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

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

1. כל קשת אדומה בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין $\displaystyle u$ ב$\displaystyle A$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
2. כל קשת שחורה בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.

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

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

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

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר 1 בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר 1 בין $\displaystyle |V|+u$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

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

משפט: מחיר המסלול הקביל הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי, קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש, מורכב משני חלקים:

1. מסלול זהה לחלוטין למסלול קביל מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי
2. מסלול בעלות 1 ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$

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

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