|
|
עמוד:238
עיגול חלול 0 מציין צומת בעל תווית זמנית ו עיגול מלא מציין צומת בעל תווית קבועה ; חץ < - מציין איזה צומת פעיל בשלב המתואר . בשלב הראשון , המתואר בחלק א של האיור , צומת A הוא הפעיל ( התווית שלו מינימלית , ( לכן מעדכנים את התוויות של B ו-כ , < שהם השכנים של , A לפי משקל הקשת המחברת אותם . A- > בכל פעם שמעדכניס תווית , מציינים מי השכן שגרס לעדכון , כדי שבסוף האלגוריתם תהיה אפשרות לשחזר את המסלול הקצר ביותר . בשלב השני , המתואר בחלק ב , בודקים את כל הצמתים בעלי התוויות הזמניות . ( כל הצמתים פרט ל ^ הם בעלי תווית זמנית . ( הצומת בעל התווית המינימלית הוא , B לפיכך צומת זה הופך לצומת הפעיל הבא , והתווית שלו הופכת לקבועה . לאחר-מכן מעדכנים את התוויות של השכנים של . B בשלב השלישי ( ראה חלק ג , ( צומת ס הופך לצומת הפעיל ומעדכנים את התוויות של השכנים של E ) D . ( 0-ו שים לב , נמצא מסלול A-o 0-ל שהוא קצר יותר מהמסלול שהיה ידוע עד כה : המסלול , ABDC שאורכו , 8 קצר יותר מהמסלול AC שאורכו . 9 כמו-כן , נמצא מסלול לצומת E ( צומת היעד ) אך מאחר שהתווית של E אינה קבועה עדיין , אין ערובה לכך שלא יימצא בהמשך מסלול מ ^ £ -ל שיהיה קצר יותר . בשלב הרביעי ( חלק ד , ( הצומת בעל התווית המינימלית הוא , C והוא הופך לצומת הפעיל . C-b אין שכנים בעלי תווית זמנית , לכן אין עדכון בשלב זה . בשלב החמישי ( חלק ה , ( הצומת המינימלי מבין בעלי התוויות הזמניות , הוא , F אשר הוא הופך לצומת הפעיל הבא . השכן היחיד של F הוא , E התווית שלו , ( 12 ) קטנה מאורך המסלול דרך . ( F ) 14 לכן התווית של E אינה מעודכנת . E הוא הצומת היחיד בעל תווית זמנית , לכן הוא הופך בשלב השישי לצומת הפעיל הבא . בפעולה זו מסתיים האלגוריתם , מפני שהתווית של צומת היעד הפכה לקבועה . המסלול ( שאפשר לשחזר לפי רישומי השכנים שליד התוויות ) הוא , ABDE ומחירו . 12
|
|