ב"רשת רחובות" המעבר מרחוב לרחוב הוא תמיד דרך כיכר. גודלו (במטרים) של רדיוס של כיכר הוא כמספר הרחובות המחוברים אל הכיכר. לדוגמה, הרדיוס של כיכר המחברת 3 רחובות הוא 3 מטרים, והרדיוס של כיכר המחברת 6 רחובות הוא 6 מטרים. הולך רגל נדרש ללכת מכיכר אחת לאחרת במסלול הקצר ביותר. המסלול הקצר ביותר הוא המסלול שבו סכום הרדיוסים של כל הכיכרות שבהן הוא עובר הוא הקטן ביותר. סכום הרדיוסים אינו כולל את הרדיוס של הכיכר שבה הוא מתחיל את מסלולו אך הוא כולל את הרדיוס של הכיכר שבה הוא מסיים את מסלולו.
נתונה רשת הרחובות NET בעיר מסוימת (גרף עם צמתים A-H).
ברשת הרחובות NET, מהו המסלול הקצר ביותר מכיכר H לכיכר C? כתבו את שמות הכיכרות במסלול זה, לפי הסדר, משמאל לימין (אין צורך לבצע מעקב).
כתבו אלגוריתם המוצא עבור רשת רחובות כלשהי את המסלול הקצר ביותר מן הכיכר K1 לכיכר K2. הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
תארו את הגרף המייצג את רשת הרחובות NET הנתונה לעיל, באופן שיתאים לאלגוריתם שכתבתם: רשמו את רשימת הצמתים ואת רשימת הקשתות עם משקליהן.
ב"רשת רחובות" המעבר מרחוב לרחוב הוא תמיד דרך כיכר. גודלו (במטרים) של רדיוס של כיכר הוא כמספר הרחובות המחוברים אל הכיכר. לדוגמה, הרדיוס של כיכר המחברת 3 רחובות הוא 3 מטרים, והרדיוס של כיכר המחברת 6 רחובות הוא 6 מטרים. הולך רגל נדרש ללכת מכיכר אחת לאחרת במסלול הקצר ביותר. המסלול הקצר ביותר הוא המסלול שבו סכום הרדיוסים של כל הכיכרות שבהן הוא עובר הוא הקטן ביותר. סכום הרדיוסים אינו כולל את הרדיוס של הכיכר שבה הוא מתחיל את מסלולו אך הוא כולל את הרדיוס של הכיכר שבה הוא מסיים את מסלולו.
נתונה רשת הרחובות NET בעיר מסוימת (גרף עם צמתים A-H).
ברשת הרחובות NET, מהו המסלול הקצר ביותר מכיכר H לכיכר C? כתבו את שמות הכיכרות במסלול זה, לפי הסדר, משמאל לימין (אין צורך לבצע מעקב).
כתבו אלגוריתם המוצא עבור רשת רחובות כלשהי את המסלול הקצר ביותר מן הכיכר K1 לכיכר K2. הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
תארו את הגרף המייצג את רשת הרחובות NET הנתונה לעיל, באופן שיתאים לאלגוריתם שכתבתם: רשמו את רשימת הצמתים ואת רשימת הקשתות עם משקליהן.
