שאלה 8 במסלול אלגוריתמים. לפניכם הגרף הממושקל G (9 קודקודים: S,B,C,D,F,G,H,I; 14 קשתות): S–B 15, B–C 4, C–D 10, S–G 2, B–G 10, C–G 7, C–H 13, H–D 6, D–I 15, S–F 30, F–G 20, G–H 8, H–I 8, F–H 13 (הקשת המעוגלת התחתונה).
שאלה 8 במסלול אלגוריתמים. לפניכם הגרף הממושקל G (9 קודקודים: S,B,C,D,F,G,H,I; 14 קשתות): S–B 15, B–C 4, C–D 10, S–G 2, B–G 10, C–G 7, C–H 13, H–D 6, D–I 15, S–F 30, F–G 20, G–H 8, H–I 8, F–H 13 (הקשת המעוגלת התחתונה).
הגרף הממושקל G (9 קודקודים S, B, C, D, F, G, H, I; 14 קשתות; S מסומן):
S–B 15 B–C 4 C–D 10
S–G 2 B–G 10 C–G 7 C–H 13 H–D 6 D–I 15
S–F 30 F–G 20 G–H 8 H–I 8 F–H 13 (הקשת המעוגלת התחתונה)
כתבו אלגוריתם המוצא בגרף ממושקל (אי-שלילי) כלשהו, שבו n קודקודים מ-v0 עד vn-1 וקודקוד בגרף – vj, את המסלולים הקצרים (הקלים) ביותר מקודקוד vj שבגרף אל שאר הקודקודים שבגרף.
מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו את תשובתכם.
בעבור גרף G הנתון, מצאו בעזרת האלגוריתם שכתבתם את המסלול הקצר ביותר מקודקוד S לכל אחד מן הקודקודים, וסרטטו טבלת מעקב כמפורט: המעקב יכלול בכל איטרציה את קבוצת הקודקודים הקבועים (שכבר ביקרנו בהם) – P ואת קבוצת הקודקודים הזמניים (שבהם עדיין לא ביקרנו) – T. נוסף על כך, בעבור כל קודקוד יצוין אורך המסלול עד אליו וזהות הקודקוד הקודם לו (ה"הורה" שלו).
בעבור גרף G הנתון, סרטטו את עץ המסלולים הקצרים (מקודקוד S).
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.