|
|
صفحة: 231
האחת - הקבוצה P ( קיצור של , permanent כלומר קבוע , ( אשר תכיל קדקודים , כך שאורך המסלול המינימלי מקדקוד המקור עד אליהם יהיה קבוע ולא ישתנה עד סוף האלגוריתם . השנייה - הקבוצה , temporaries ) T כלומר זמניים ) אשר תכיל קדקודים כך שאורך המסלול המינימלי מקדקוד המקור עד אליהם יהיה זמני ועשוי להשתנות עד סוף האלגוריתם . מאחר שאין מסלולים מעגליים בעלי אורך אי-חיובי , המסלול בעל האורך המינימלי מקדקוד המקור לעצמו הוא , 0 והערך הזה לא ישתנה עד סוף האלגוריתם . לכן , כיוון שהקדקוד 0 הוא קדקוד מקור , בתחילת האלגוריתם ישתייך הקדקוד 0 לקבוצה P ויתר הקדקודים ישתייכו לקבוצה J עבור כל קדקוד u ברשת נרצה לשמור את אורך המסלול הקצר ביותר מקדקוד המקור 0 לקדקוד u ואותו נסמן ב- d [ u ] ( לציון המילה , distance כלומר , מרחק . ( בתחילת האלגוריתם , לכל קדקוד , « פרט לקדקוד המקור , נבצע את ההשמה ו d [ u ] < - 00 40 ] < - 0-1 מאחר שאורך המסלול הקצר ביותר מקדקוד המקור לעצמו הוא . 0 כמו כן , נרצה לשמור לגבי כל קדקוד מידע על זהות הקדקוד הקודם לו ( ההורה שלו ) במסלול הקצר ביותר . לאור זאת , נשתמש במערך Pa ( המציין , parent כלומר , הורה , ( כך שלכל קדקוד u ברשת Pa [ u ] מציין קדקוד שממנו הגענו לקדקוד . « בתחילת האלגוריתם לכל קדקוד , u פרט לקדקוד המקור , נבצע את ההשמה Pa [ u ] < - '_ ' ( המציין , undefined כלומר עדיין לא מוגדר . ( לגבי קדקוד המקור 0 נבצע : , Pa [ 0 ] < - nil המציין שלקדקוד המקור אין הורה . לאור האמור לעיל , בתחילת האלגוריתם יש לבצע את סדרת ההוראות שלהלן T = {\ , 2 , , « -1 } -1 P < - { 0 ) d [ O ] < - 0 ? לכל קדקוד j שאינו קדקוד מקור , כלומר לכל j = 1 ... « -1 בצע : , d [ j ] < - a Oj מאחר ש- aQ j מתאר את אורך המסלול המינימלי הזמני העובר דרך הקשת מקדקוד המקור 0 לקדקוד p [ 0 ] < - nil לכל קדקוד שאינו קדקוד מקור , כלומר לכל OH j = 1 ... /; -1 קיימת קשת ( 0 , j ) אז בצע : Pa \ j ] < - ' 0 '
|
|