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

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

אנא תאר אלגוריתם כזה, ונתח את סיבוכיותו.

דוגמה: בגרף הבא, הקשתות המודגשות שחורות, וצומת המוצא הוא 1. הבעייה. בגרף זה, המסלול הקביל הזול ביותר מ1 ל4 הוא $\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4$, ועלותו 14. שים לב שהמסלול $\displaystyle 1\rightarrow 6\rightarrow 7\rightarrow 3\rightarrow 4$ אמנם זול יותר, אך פשוט אינו קביל. באותו אופן, אין מסלול קביל מ1 ל6, ולכן עלות 6 היא $\displaystyle \infty$.