היי,
אני עובר שוב על הדוגמה בספר של קורמן, ומשהו לא מסתדר לי בפסאודו קוד.
לפי הפסאודו קוד - אני מאתחל את הערך של כל הצמתים לאינסוף, למעט הצומת שבחרתי להתחיל בו - שאותו אני מאתחל לאפס.
אני בוחר את הצומת המינימלי - זה שאתחלתי קודם לאפס, ומתחיל לעבור על ה adjacency list שלו.
עכשיו, במהלך הלולאה הזו, אני בודק אם הצומת שייך ל q - והוא אכן שייך, והאם הערך של הקשת קטן מהערך של הצומת - שזה תמיד מתקיים כי הוא מאותחל לאינסוף.
אבל פה יש פער - אם במקרה ב adjacency list הקשת הכבדה יותר הייתה מופיעה אחרי הקשת הקלה יותר, הרי שהייתי מקבל עץ שגוי - כי pai [V] היה מוגדר
לקשת האחרונה שבדקתי, ולא לקשת הקלה ביותר.
איך זה מתיישב?
תודה מראש!