שאלה בגרפים

[yayaya]

שאלה בגרפים

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

 

[yayaya]

בין s ל-b יותר הגיוני ..

אבל אני מקווה שעיקרון השאלה ברור ...

 

[GuestOfHonor]

המממ גרפים...

לא נגעתי בזה סמסטר שלם, אז אני מקווה שאני לא מתבלבל. גם בדייקסטרה וגם בבלמן פורד, יש לך מקור יחיד (s), ואתה שומר מידע נוסף עבור כל קודקוד בגרף. חלק מהמידע הזה זה Pi - להלן הPrdecessor. זהו 'מצביע' לקדקוד אחר בגרף, או לחילופין null אם מדובר בs או בקדקוד שלא ניתן להגיע אליו מs. המשמעות של הpredecessor של קדקוד V כלשהו היא : "מי הקודקוד שנמצא ישר לפני V, במסלול הכי קצר שמגיע מs אל V". לאחר הרצת האלגוריתם, אתה ניגש לd שלך, בודק מי ה predecessor שלו, ואז בודק עבור הpredecessor מי הpredecessor שלו, וכן הלאה וכן הלאה. ככה אתה בונה את המסלול מהסוף להתחלה. הסבר טוב לזה ניתן למצוא גם בספר Introduction to algorithms של Cormen ושות'.