מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Dijkstra/תרגילים/מציאת מסלול זול בגרף בעל קשתות בתחום שלם קטן/תשובה

נבנה גרף חדש $\displaystyle G'=(V',E')$ ברשימת שכנויות.

נגדיר את הגרף החדש מתוך $\displaystyle G=(V,E)$ כלהלן. ראשית, אם $\displaystyle V=\{1,...,n\}$, אז נקבע $\displaystyle V'=\{1,...,n\}$. כעת נעבור על כל $\displaystyle e\in E$. אם מחיר קשת $\displaystyle e$ הוא 1, נוסיף קשת זו ל$\displaystyle E'$.

לחלופין, נניח שמחיר הקשת $\displaystyle e=(u,v)$ הוא $\displaystyle k>1$. במקרה זה נוסיף עוד $\displaystyle k-1$ צמתים חדשים ל$\displaystyle V'$ ועוד $\displaystyle k$ קשתות ל$\displaystyle E'$, כך שיש מסלול באורך $\displaystyle k$ מ$\displaystyle u$ ל$\displaystyle v$ של קשתות במחיר 1 ב$\displaystyle G'$. נקבל ב$\displaystyle G'$ גרף בעל מסלולים במחיר 1 בלבד.

דוגמה: בתרשים הבא, הגרף העליון הוא $\displaystyle G$, הגרף המקורי. הגרף התחתון הוא $\displaystyle G'$ הגרף החדש (הצמתים המקוריים מ$\displaystyle G$ מסומנים בהדגשה). הפיכת Dijkstra לBFS.

המשפט הבא טריביאלי:

משפט: לכל $\displaystyle u\in V$, מחיר המסלול הזול מ$\displaystyle s$ ל$\displaystyle u$ ב$\displaystyle G$ הוא מרחק המסלול הקצר מ$\displaystyle s$ ל$\displaystyle u$ ב$\displaystyle G'$.

קל גם להווכח שסיבוכיות בניית $\displaystyle G'$ היא $\displaystyle O(k\cdot (|V|+|E|))=O(|V|+|E|)$. כעת נריץ את אלגוריתם [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] על $\displaystyle G'$. הסיבוכיות הכוללת (של הבניה ושל ההרצה) במקרה הגרוע היא $\displaystyle \Theta (k\cdot (|V|+|E|))=\Theta (|V|+|E|)$.