ראשי > מסלולים קצרים > טכניקת ההקלה

טכניקת ההקלה

דוגמאות הרצה

על מנת להבין את האלגוריתמים הבאים יש להבין את העיקרון החשוב של טכניקת ההקלה. ולכן נתעכב כדי להדגים את המקרים הנפוצים של טכניקת ההקלה בשלוש דוגמאות שונות.

דוגמא ראשונה

דוגמא שנייה

דוגמא שלישית

סיכום טכניקת ההקלה

כל אחד מהאלגוריתמים בפרק זה, קורא בתחילתו לפונקציה INITIALIZE-ESTIMATES, ולאחר מכן, מבצע פעם אחר פעם הקלה על הקשתות.
טכניקת ההקלה היא האמצעי היחיד לשינוי אומדני המסלולים הקצרים ביותר.
האלגוריתמים השונים נבדלים זה מזה במספר הפעמים שבו הם מבצעים הקלות על קשתות הגרף ובסר שבו הם עושים אותן.
באלגוריתם של דייקסטרה ובאלגוריתם למציאת מסלולים קצרים ביותר בגרף מכוון חסר מעגלים, על כל קשת מתבצעת בדיוק הקלה אחת, לעומת זאת, באלגוריתם בלמן-פורד, מתבצעות על כל קשת מספר הקלות.