מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם 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,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.
2. במקום כל קשת $\displaystyle (u,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
3. במקום הקשת השלילית $\displaystyle (x,y)$ (בגרף המקורי), נמתח קשת מהצומת המתאים ל$\displaystyle x$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle y$ ב$\displaystyle B$ במחיר 0. התרשים הבא מראה זאת.

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

נניח שלקשת השלילית היה מחיר $\displaystyle -z$. בנוסף נמתח עוד שני סוגי קשתות:

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

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

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

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

הוכחה: בגרף המקורי, ייתכן שהמסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ לא השתמש בקשת השלילילת, וייתכן שהשתשמש בו. במקרה הראשון, תהיה קפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$, ובמקרה השני, תהיה קפיצה מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$. הקפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$ עולה $\displaystyle z$ יותר מאשר המסלול המקורי. הקפיצות מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$ גם כן עולות $\displaystyle z$ יותר מאשר המסלול המקורי, שכן עלות כל אחת משתי הקשתות היא 0, והנוסע לא קיבל את התשלום $\displaystyle z$ מהחברה.

כעת כל הקשתות אינן שליליות, ומותר להריץ את Dijkstra.

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