|
|
עמוד:255
להלן הסבר של צעדי האלגוריתם ? . צעד 1 א . נתבונן בגרף הזה : נניח שקדקוד המקור הנו . S = 1 קל לראות שמקדקוד המקור S לא ניתן להגיע לקדקודים שמספרם 3 . 4-ו לכן ברור כי הערך של dist [ 3 ] הוא , 00 כיוון שלא קיים מסלול מהקדקוד 1 לקדקוד . 3 לאור זאת , נחליט שבתחילת האלגוריתם לכל קדקוד , v פרט למקור , נבצע את ההצבה ; IONV , distfv ] ?< - 00 שלא ידוע מראש אם קיים מסלול באורך כלשהו מקדקוד המקור S לקדקוד כלשהו . v במהלך האלגוריתם נרצה לשפר את אורך המסלול מקדקוד המקור 5 לקדקוד , \ ' לכל . v & v ב . אם לא קיים מסלול באורך כלשהו מקדקוד המקור S לקדקוד כלשהו , v אז לקדקוד הזה אין הורה P [ v ] < - NIL ) או \ P \ v \ = 0 לפיכך , בתחילת האלגוריתם לאף קדקוד אין הורה , כיוון שתהליך הסריקה עדיין לא התחיל . לכן נבצע את ההצבה הבאה לכל קדקוד . P [ v ] = veV- { S ) ג . ברור כי לכל קדקוד : rmm TIN 1 m 3 v e v- { 5 ) , Used [ v ] < - FALSE כיוון שבתחילת האלגוריתם עדין לא גילינו את צומתי הגרף ( ביקרנו בהם . ( צעד 2 מיותר להסביר מדוע אורך המסלול מקדקוד המקור S לעצמו הנו . 0
|
|