שאלה 8אלגוריתמיקה2023 קיץ מועד אמסלולים קצרים במשקלות אי־שליליים (דייקסטרה)סה״כ 25 נק׳
אלגוריתם למסלול קצר ברשת רחובות וכיכרות
ב"רשת רחובות" המעבר מרחוב לרחוב הוא תמיד דרך כיכר.
גודלו (במטרים) של רדיוס של כיכר הוא כמספר הרחובות המחוברים אל הכיכר.
לדוגמה, הרדיוס של כיכר המחברת 3 רחובות הוא 3 מטרים, והרדיוס של כיכר המחברת 6 רחובות הוא 6 מטרים.
✎ דוגמה
לפניכם סרטוט של רשת רחובות. בתוך כל כיכר מצוין הרדיוס של אותה הכיכר.
רשת רחובות לדוגמה: ארבע כיכרות שרדיוסיהן 2, 2, 3, 1
לפניכם רשת הרחובות NET בעיר מסוימת:
רשת הרחובות NET: הכיכרות A עד I והרחובות המחברים ביניהן
הולך רגל נדרש ללכת מכיכר אחת לאחרת במסלול הקצר ביותר.
המסלול הקצר ביותר הוא המסלול שבו סכום הרדיוסים של כל הכיכרות שבהן הוא עובר הוא הקטן ביותר.
סכום הרדיוסים אינו כולל את הרדיוס של הכיכר שבה הוא מתחיל את מסלולו אך הוא כולל את הרדיוס של הכיכר שבה הוא מסיים את מסלולו.
✎ דוגמה
בסרטוט שלעיל של רשת הרחובות NET מודגש המסלול הקצר ביותר מן הכיכר A לכיכר E.
גודל הרדיוסים במסלול זה הוא 3+2+3 וסכומם הוא 8. סכום זה הוא הקטן ביותר מבין כל האפשרויות.
משימות
אמשימה א
מעקב34%
ברשת הרחובות NET, מהו המסלול הקצר ביותר מכיכר H לכיכר C? כתבו את שמות הכיכרות במסלול זה, לפי הסדר, משמאל לימין (אין צורך לבצע מעקב).
ב(1)משימה ב(1)
תשובה33%
כתבו אלגוריתם המוצא עבור רשת רחובות כלשהי את המסלול הקצר ביותר מן הכיכר K1 לכיכר K2.
⚠ הערה — אילוץ מחייב
יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
ב(2)משימה ב(2)
תרשים33%
סרטטו את הגרף המייצג את רשת הרחובות NET הנתונה לעיל, באופן שיתאים לאלגוריתם שכתבתם.
שפת התכנות שלי
שאלה 8אלגוריתמיקה2023 קיץ מועד אמסלולים קצרים במשקלות אי־שליליים (דייקסטרה)סה״כ 25 נק׳
אלגוריתם למסלול קצר ברשת רחובות וכיכרות
ב"רשת רחובות" המעבר מרחוב לרחוב הוא תמיד דרך כיכר.
גודלו (במטרים) של רדיוס של כיכר הוא כמספר הרחובות המחוברים אל הכיכר.
לדוגמה, הרדיוס של כיכר המחברת 3 רחובות הוא 3 מטרים, והרדיוס של כיכר המחברת 6 רחובות הוא 6 מטרים.
✎ דוגמה
לפניכם סרטוט של רשת רחובות. בתוך כל כיכר מצוין הרדיוס של אותה הכיכר.
רשת רחובות לדוגמה: ארבע כיכרות שרדיוסיהן 2, 2, 3, 1
לפניכם רשת הרחובות NET בעיר מסוימת:
רשת הרחובות NET: הכיכרות A עד I והרחובות המחברים ביניהן
הולך רגל נדרש ללכת מכיכר אחת לאחרת במסלול הקצר ביותר.
המסלול הקצר ביותר הוא המסלול שבו סכום הרדיוסים של כל הכיכרות שבהן הוא עובר הוא הקטן ביותר.
סכום הרדיוסים אינו כולל את הרדיוס של הכיכר שבה הוא מתחיל את מסלולו אך הוא כולל את הרדיוס של הכיכר שבה הוא מסיים את מסלולו.
✎ דוגמה
בסרטוט שלעיל של רשת הרחובות NET מודגש המסלול הקצר ביותר מן הכיכר A לכיכר E.
גודל הרדיוסים במסלול זה הוא 3+2+3 וסכומם הוא 8. סכום זה הוא הקטן ביותר מבין כל האפשרויות.
משימות
אמשימה א
מעקב34%
ברשת הרחובות NET, מהו המסלול הקצר ביותר מכיכר H לכיכר C? כתבו את שמות הכיכרות במסלול זה, לפי הסדר, משמאל לימין (אין צורך לבצע מעקב).
ב(1)משימה ב(1)
תשובה33%
כתבו אלגוריתם המוצא עבור רשת רחובות כלשהי את המסלול הקצר ביותר מן הכיכר K1 לכיכר K2.
⚠ הערה — אילוץ מחייב
יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
ב(2)משימה ב(2)
תרשים33%
סרטטו את הגרף המייצג את רשת הרחובות NET הנתונה לעיל, באופן שיתאים לאלגוריתם שכתבתם.
