|
|
صفحة: 233
עתה , השאלה המרכזית היא . כיצד משפרים את המסלולים מקדקוד המקור 0 ליתר הקדקודים , כך שהאורכים שלהם יהיו מינימליים ? בשיטה זו בכל איטרציה נבצע שני צעדים . א > טרציה ראשונה צעד ראשון נמצא קדקוד , מבין הקדקודים "הזמניים" שבקבוצה » בעל אורך המסלול המינימלי הזמני הקטן ביותר מקדקוד המקור עד אליו . נכנה את הקדקוד הזה בשם . K בדוגמה שלנו , K = 2 מאחר d [ 2 ] = 2-ש 42 ] -ול הערך הקטן ביותר מבין כל d [ v ] -n עבור . ve T כעת , נצרף את הקדקוד K לקבוצה ק , ונוריד אותו מהקבוצה J כלומר המרחק המינימלי מקדקוד המקור עד אליו הוא קבוע ואינו משתנה עד סוף האלגוריתם . אי לכך , בדוגמה שלנו = { 1 , 3 , 4 , 5 } p = { 0 , 2 } 7 צעד שני בצעד הזה נבדוק אם ניתן לשפר את האורכים של המסלולים הקצרים בעזרת מסלולים העוברים דרך הקדקוד , K = 2 שנקבע בצעד הראשון , מקדקוד מקור 0 לכל קדקוד J כאשר ? jeT ? . בדוגמה שלנו אורך המסלול מקדקוד המקור 0 לקדקוד , 1 העובר דרך הקדקוד fK = 2 הוא , ( 6 + 2 = ) 8 לעומת 5 שהוא אורך המסלול מקדקוד המקור 0 לקדקוד 1 שאינו עובר דרך הקדקוד . K = 2 מאחר , 8 > 5-ש אין שיפור באורך המסלול מקדקוד המקור 0 לקדקוד , 1 העובר דרך הקדקוד . 2
|
|