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