גרפים›מסלולים קצרים ביותר

ב'רשת רחובות' המעבר מרחוב לרחוב הוא תמיד דרך כיכר. גודלו (במטרים) של רדיוס כל כיכר הוא כמספר הרחובות המחוברים אל הכיכר (לדוגמה, כיכר המחברת 3 רחובות - רדיוסה 3 מטרים; כיכר המחברת 6 רחובות - רדיוסה 6 מטרים). הולך רגל נדרש ללכת מכיכר אחת לאחרת. המסלול הקצר ביותר הוא זה שבו סכום הרדיוסים של כל הכיכרות שהמסלול עובר בהן הוא הקטן ביותר. סכום הרדיוסים אינו כולל את רדיוס הכיכר שבה מתחיל המסלול, אך כולל את רדיוס הכיכר שבה מסתיים המסלול. לפניכם רשת רחובות NET בעיר מסוימת, ובה הכיכרות A-I.

רשת הרחובות NET (קריאה מאומתת של האיור הווקטורי הנקי בשאלון, ברמת ודאות גבוהה): הרחובות (קשתות דו-כיווניות, כל אחת בין שתי כיכרות) הם A-B, A-F, B-C, B-F, C-E, D-F, E-F, E-G, F-G, F-H, F-I, G-H — 12 רחובות בסך הכול. הרדיוס של כל כיכר (=מספר הרחובות המחוברים אליה): A=2, B=3, C=2, D=1, E=3, F=7, G=3, H=2, I=1 (F מצוירת הגדולה ביותר בשאלון, ואכן בעלת הרדיוס הגבוה ביותר ברשת). לדוגמה, כפי שמצוין בשאלון עצמו: המסלול הקצר ביותר מכיכר A לכיכר E הוא A→B→C→E, שסכום רדיוסיו (ללא A, כולל E) הוא 3+2+3=8.

רשימת שכנויות (רשת NET):
A: B, F
B: A, C, F
C: B, E
D: F
E: C, F, G
F: A, B, D, E, G, H, I
G: E, F, H
H: F, G
I: F

סעיף א

ברשת הרחובות NET, מהו המסלול הקצר ביותר מכיכר H לכיכר C? כתבו את שמות הכיכרות במסלול זה, לפי הסדר, משמאל לימין (אין צורך לבצע מעקב).

סעיף ב

כתבו אלגוריתם המוצא, עבור רשת רחובות כלשהי, את המסלול הקצר ביותר (לפי הגדרת השאלון - סכום רדיוסי הכיכרות במסלול) מכיכר K1 לכיכר K2. הערה: יש לכתוב אלגוריתם שיעיל ככל האפשר, שאינו עובר על כל המסלולים האפשריים. (השאלון אינו נותן חתימה מדויקת - להלן חתימה סבירה שנבחרה כדי לאפשר בדיקה אוטומטית, המייצגת את הרשת כרשימת שכנויות ואת רדיוס כל כיכר בטבלה נפרדת.)

public static List<string> ShortestPath (Dictionary<string, List<string>> adj, Dictionary<string, int> radius, string k1, string k2)

סעיף ג

סרטטו את הגרף המייצג את רשת הרחובות NET הנתונה, באופן שיתאים לאלגוריתם שכתבתם.

שאלות ותגובות על השאלה

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה לתכנות עונה כאן — תקבלו מענה מקצועי

לתרגל עוד שאלות — חינם ←