|
|
עמוד:240
לאחר ביצוע האלגוריתם אפשר לעדכן את טבלאות הניתוב של כל הצמתים לאורך הנתיב שנמצא . שאלה 4 . 14 א . הפעל את האלגוריתם של דייקסטרה באופן ידני על הגרף שהובא בשאלה . 4 . 13 ב . להלן גרף נוסף ( איור ( 4 . 23 המייצג רשת תקשורת פשוטה . מצא , באמצעות הפעלה ידנית של , את המסלולים הקצרים ביותר בין כל הצמתים , ובנה טבלאות ניתוב לכל הצמתים ברשת . מהו המסלול בין F- ^ A ומה מחירו ? להלן תיאור פורמלי של האלגוריתם של דייקסטרה ואחריו הוכחה שהוא אמנם מוצא את המסלול הקצר ביותר . Tj-j 6 op »? < fe pj v-i ) - ? . נתונים : גרף מכוון בעל קבוצת צמתים V וקבוצת צלעות E לכל צלע e נתון מחיר 1 ( e ) > 0 צומת התחלה s צומת היעד t ( מניחים שקיים מסלול בין s ל- ( t נשתמש במשתנים : - T קבוצת צמתים בעלי תווית זמנית ( בקיצור ו קבוצת צמתים ( 'זמניים' - P קבוצת צמתים בעלי תווית קבועה ( בקיצור י קבוצת צמתים ( 'קבועים' - A . ( v ) תווית של צומת v - N ( v ) השכן דרכו מגיעים לצומת v איור 4 . 23 גרף המייצג רשת תקשורת
|
|