מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם 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$, נמתח קשת במחיר $\displaystyle 1$ בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle x+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$, אם החלק הראשון זוגי, ומסלול בעלות $\displaystyle x+1$, אם החלק הראשון אי-זוגי.

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

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