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

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

אנא תאר אלגוריתם המקבל כקלט את הגרף, טבלת עלויות לקשתות, וגודל הקנס, ומוצא את מחיר המסלול הזול ביותר (במובן שאותו הסברנו כרגע) לכל צומת $\displaystyle u$. אנא הוכח נכונות ונתח סיבוכיות.