|
|
עמוד:211
5 . 1 דוגמאות של בעיית המסלול הקצר ביותר דוגמה 5 . 1 נהג רוצה למצוא את הדרך הקצרה ביותר מרחוב אחד לרחוב אחר בעיר מסוימת . לרשות הנהג מפת כבישים של העיר , שבה הוא נמצא , אשר מצוינים בה המרחקים בין כל שתי כתובות . המטרה של הנהג היא לקבוע איזה מסלול נסיעה הוא הקצר ביותר . במקרה הזה , כל צומת יכול להיות קדקוד בגרף . הכבישים הם הקשתות . כביש חד-סטרי יכול להיות קשת מכוונת , וכביש דו-סטרי בין שתי הכתובות A 5-ו יכול להיות קשת בלתי מכוונת בין הקדקודים A 5-ו או שתי קשתות מכוונות מהקדקוד A לקדקוד B ולהפך , כלומר שתי קשתות מכוונות בין ^ -ל בעלות כיוונים מנוגדים . ^ איור 5 . 1 מתאר את מפת הכבישים בעיר הזאת . לכל קשת מיוחס מספר אשר מייצג את המרחק ( במטרים ) ומספרים אלו רשומים בצד הקשתות . הקדקודים של הגרף מייצגים את נקודות ההצטלבות . פרק . 5 בע"ת המסלול הקצר ביותר בפרק הקודם הצגנו את בעיית המסלול הקצר באופן בסיסי ביותר . בפרק הזה נציג וננתח שיטות שונות לפתרון בעיות המסלול הקצר ביותר , ונחקור את סיבוביות זמן הריצה שלהן . בטרם נציג את הפתרונות ( אלגוריתמים ) השונים לבעייה הנדונה , נראה מספר דוגמאות לבעיית המסלול הקצר ביותר ( נוספות על זו שהצגנו בפרק הקודם . (
|
|