|
|
עמוד:237
בכל שלב של האלגוריתם מתבצעות הפעולות האלה : . 1 מוצאים את הצומת בעל התווית הזמנית הקטנה ביותר בגרף כולו . . 2 הופכים צומת זה לפעיל ואת התווית שלו הופכים לקבועה . . 3 בוחנים את כל השכנים של הצומת הפעיל ומעדכנים את התוויות שלהם , לפי משקל הצלע המחברת אותם לצומת הפעיל . עדכון פירושו ו אס משקל המסלול , S-z > העובר דרך הצומת הפעיל , קטן מהתווית של הצומת , יש לשנות את התווית לערך הנמוך יותר . פעולות אלה יתבצעו עד שהתווית של צומת היעד תהפוך לקבועה . נדגים את פעולתו של האלגוריתם על הגרף הנתון באיור . 4 . 21 נניח שרוצים למצוא את המסלול הקצר ביותר מצומת A לצומת . E בשלב ההתחלתי , התווית של A היא קבועה וערכה הוא 0 ( המרחק של צומת מעצמו הוא . ( 0 באיור 4 . 22 מתואר ביצוע האלגוריתם של דייקסטרה על גרף זה . אנו משתמשים במוסכמות הסימון האלה נ ליד כל צומת רשומים ( בסוגריים ) התווית של הצומת והצומת השכן שדרכו מגיעים לצומת במסלול המינימלי הידוע ( זה שאורכו נתון בתווית . ( בשלב ההתחלתי לא ידוע מסלול כלשהו , לכן הסימון ההתחלתי של הצמתים הוא , ( - , 00 ) כלומר , התווית אינסוף ולא ידוע מי הצומת השכן . איור 4 . 21 גרף משוקלל להדגמת פעולתו של האלגוריתם של דייקסטרה
|
|