|
|
עמוד:312
עתה ניתן לבצע את הבדיקה הבאה ; ל 0 יכום האי 0 רציה השלישית : כך ממשיכים לבצע את האיטרציות . באיטלציה ה- ית- /« נרשה שהמסלול / -מ אל . / יעבור דרך הקדקוד . m נתבונן בביטוי הזה ו שהנו משקל המסלול הקצר ביותר מקדקוד ; אל קדקוד , j שרשאי לעבור רק דרך קדקודי הביניים השייכים לקבוצה . { 1 , 2 ,..., " !} יעילות האלגוריתם של פלויד-וולשל נתון הגרף , G = ( V , E ) כאשר . \ v \ = n בצעד ! נדרש זמן 0 ( n ) כיוון שבשלב זה מעתיקים מטריצה אחת לאחרת . בצעד 2 נדרש זמן O ( t ?) שכן מבוצעות בו 3 לולאות מקוננות . בצעד 4 נדרש זמן , 0 { n ) כיוון שבשלב הזה מעתיקים מטריצה אחת לאחרת . 3 לסיכום : האלגוריתם רץ אפוא בזמן , 0 (« ) לעומת האלגוריתם של בלמן-פורד , הרץ באותם תנאים בזמן . 0 ( n ) נדגים את ההרצה של האלגוריתם פלויד-וורשל על הרשת שלהלן ו
|
|