שאלה ממבחן
שלום,
שאלה ממבחן,
בהנתן גרף קשיר פשוט וזוג צמתים עם משקל חיובי, נרצה למצוא את המסלול הקל ביותר בין זוג הצמתים s,t שעובר לכל היותר דרך 2 קשתות מקבוצה נתונה של קשתות 'E
הפתרון שהוצע הוא על ידי פיצול קדקודים, רציתי לשאול מדוע הפתרון הבא אינו נכון
נמצא את המשקל המקסימלי של אחת הקשתות בגרף
נוסיף את המשקל הזה רק לקבוצת הקשתות 'E
נריץ דייקסטרה מהצומת s
אם יש 2 קשתות או יותר מהקבוצה 'E
נחזיר שאין מסלול תקין
מבחינת נכונות דייקסטרה מוצא מסלול קל ביותר בין זוג צמתים בגרף קשיר
הקשתות של הקבוצה 'E
הן ממשקל מקסימלי בגרף ולכן אם נעבור דרכן הן בהכרח חלק מכל מסלול בין זוג הצמתים בגרף לפני הוספת המשקל
אשמח להכוונה האם הטענה נכונה, או שפספסתי משהו
תודה רבה