|
|
עמוד:307
ב . המשקל על הקשת יכול להיות חיובי או שלילי , אולם הגרף אינו מכיל מעגלים בעלי משקל שלילי . ג . נגדיר : d משקל המסלול הקצר ביותר מהקדקוד / אל הקדקוד . j ^ ד . כמו כן , נגדיר - dj '' l ) משקל המסלול הקצר ביותר מהקדקוד / אל הקדקוד r כאשר כל קדקודי הביניים במסלול הזה שייכים לקבוצה . { 1 , 2 , m-1 } כלומר המסלול הזה לא יעבור דרך הקדקודים , שמספרם . my » 1-12 v קל לראות כי dj ° ? mr dj .-כי הוא משקל המסלול הקצר ביותר מהקדקוד / אל הקדקוד j אשר כל קדקודי הביניים בו היא קבוצה ריקה , כלומר המסלול הזה לא יעבור דרך הקדקודים שמספרם 1-מ עד . « ולכן : מחד ' M הנו משקל המסלול הקצר מהקדקוד / אל הקדקוד , j כך שהמסלול אינו עובר דרך אף קדקוד אחר של הגרף . מאידך , w מתאר את משקל המסלול הקצר הזמני כאשר המסלול הזה אינו עובר דרך אף קדקוד אחר של הגרף . כלומר , המסלול המינימלי הזמני מכיל רק קשת ישירה ( אם היא קיימת בכלל ) מקדקוד / אל קדקוד J והמשקל שעל הקשת הזאת רשום במטריצה וניןזדו אס הקשת f ee לא קיימת , אז ל- nc ניתן הערך הגרוע ביותר שהוא 00 ( כמו הערך של ? K נניח שמספר הקדקודים בגרף הוא \ V \ = n והם ממוספרים 1-מ עד . « עתה נתבונן בכל המסלולים הקצרים ביותר מהקדקוד 1 לקדקוד ? . j בהתחלה במסלול הזה אין קדקודי ביניים . אם קיימת קשת >! / -מ ד , אזי משקל המסלול המינימלי / -מ . / -ל יהיה המספר שרשום בצד קשת זו , אחרת יהיה ערכו . 00 2 /> באיטרציה הראשונה - נרשה שהמסלול יעבור דרך הקדקוד . 1 עתה נתבונן בביטוי ; , dJ שהנו משקל המסלול הקצר ביותר מהקדקוד r אל הקדקוד j שאינו עובר דרך הקדקודיס שמספרם 2-מ עד . n כלומר , המסלול הזה רשאי לעבור דרך קדקודי הביניים השייכים לקבוצה . { 1 } ייתכן שהמסלול הזה יעבור דרך הקדקוד , 1 ואז המסלול ייראה כך , / - > 1 - > j או שהמסלול הזה לא יעבור דרך הקדקוד , 1 ואז המסלול ייראה כך ן / J כזכור , dJ- מתאר את משקל המסלול . / - ? . / ו- J 1 מתאר את משקל המסלול . / - ^ l « -i dJ / + ^ 1
|
|