לפתרון בעיית מסלולים
קצרים ביותר ישנם שימושים רבים מספור. דוגמא בסיסית לבעיה
טמונה בסיפור הבא: חברת משלוחים כלל עולמית (כמו UPS)
מעונינת להשתמש בטיסות סדירות על מנת לבצע את משלוחיה ברחבי
העולם. החברה מחזיקה טבלה שבה רשומים מחירי הטיסות בין כל
היעדים שבינהם יש טיסות ישירות. כאשר החברה מעונינת לבצע
משלוח בין תל-אביב לינגון (בירת מינמר הלא היא בורמה לשעבר)
היא מעוניינת לדעת מהו המסלול בעל העלות הנמוכה ביותר לביצוע
המשלוח.
דרך אפשרית אחת לבירור
המסלול הקצר ביותר היא כמובן הכנת רשימה של כל המסלולים
האפשרים וחישוב עלות כל אחד מהם. אולם דרך זו בזבזנית ביותר
- קיימים מאות מסלולים אפשריים ורבים מהם אין טעם כלל לבחון:
ברור כי כל מסלול המתחיל בטיסה ת"א-פורטלנד יורד מן
הפרק.
ייצוג גרפי
בעיה זאת היא קלאסית לייצוג
ע"י גרפים ממושקלים: כל קודקוד מייצג יעד, כל קשת מייצגת
קיום נתיב בין שני יעדים וכל קשת בעלת משקל המייצג את העלות
של לקיחת נתיב זה.
גרסאות שונות של הבעיה
קיימות מספר ווריאציות לבעית
המסלול הקצר ביותר: מציאת מסלולים קצרים ביותר ממקור
יחיד היא הבעיה הראשונה אותה ננתח - בהינתן גרף וקודקוד
s אנו מעוניינים למצוא המסלולים
הקצרים ביותר בין s לבין כל הקודקודים
בגרף. הבעיה של מסלולים קצרים ביותר ליעד יחיד היא
למעשה בדיוק אותה בעיה לאחר היפוך כל הקשתות בגרף. הבעיה
של מסלולים קצרים ביותר בין כל זוגות הקודקודים בגרף:
בעיה זאת ניתן לפתור ע"י פתרון הבעיה הראשונה עבור
כל אחד מהקודקודים בגרף, אולם קיימת דרך אלגנטית יותר לפתור
זאת.
מה בפרק
האלגוריתמים למציאת מסלולים
קצרים ביותר מתבססים רובם על טכניקת
ההקלה ואיתה נתחיל את הפרק. לאחר מכן נציג את האלגוריתם
של דייקסטרה הפותר את הבעיה כאשר כל המשקולות בגרף הם
אי-שליליים, אח"כ נעבור לאלגוריתם
של בלמן-פורד הפותר מקרה כללי יותר (בו קשתות יכולות
להיות בעל משקל שלילי), ובסוף נראה גם אלגוריתם
בזמן-לינארי לחישוב מסלולים קצרים ביותר ממקור יחיד
בגרף מכוון ללא מעגלים.
