|
|
صفحة: 239
דרך הקשתות המודגשות ניתן לראות את אורך המסלול המינימלי מקדקוד המקור 0 לכל קדקוד אחר ברשת . כמו כן , ניתן לקבוע מהו המסלול עצמו . כך , למשל , עבור המסלול 0 > 5 יהיה המסלול ( מהסוף להתחלה ) כדלקמן ו קודם הקדקוד , 5 ההורה של 5 הנו , 3 וההורה של 3 הוא , 1 וההורה של 1 הוא הקדקוד , 0 ולקדקוד 0 אין הורה , כיוון שהוא קדקוד המקור . לפיכך המסלול הוא : Q- > 1 - > 3- > 5 עתה נוכל לסכם את האלגוריתם כדלהלן ו אתחול : צעד 0 = { 1 , 2 ,...., « -1 } 0 . 1 י P = { 0 } 7 d [ Q ] < r- 0 0 . 2 0 . 3 לכל קדקוד , שאינו קדקוד מקור , כלומר , לכל 7 = 1 , /! -1 בצע d \ j ] ^ a [ 0 J ] 0 . 4 סוף הלולאה . ;/ M 0 ]< -nil 0 . 5 0 . 6 לכל קדקוד j = 1 , ...., « -1 בצע : אם קיימת קשת ( 0 J ) אז בצע Pa [/] < - ' 0 ' 1 אחרת - בצע Pa \ j ] < - ' - ' ; 0 . 7 סוף לולאה .
|
|