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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

נתון גרף מכוון וקשיר מצומת כלשהו. לכל קשת יש מחיר. רוצים למצוא את המסלול הזול ביותר מs לכל צומת u כלשהו, אך תחת העדפה למסלולים שארכם זוגי. מציין גודל קנס כלשהו. אם מסלול כלשהו מ ל הוא אי-זוגי, יש להוסיף למחיר מסלול זה קנס בגובה .

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