|
|
עמוד:306
ראינו בסעיף , 5 . 4 כי סיבוביות זמן הריצה של האלגוריתם דיקסטרה , הפותר את בעיית המסלולים הקצרים ביותר מקדקוד מקור יחיד , היא . O (| V | ) לפיכך , סיבוביות זמן הריצה של האלגוריתם הנדון היא , 0 (| V | ) כי צעד : 1 דורש זמן O (\ V \) צעד : 2 דורש זמן O (| v | 2 ) צעד : 3 דורש זמן 0 (| v'p ) = O (\ v \ ? | v | 2 ) וסיבוכיות זמן הריצה הכללית הנה : O {\ V \) + O (\ V \ 2 ) + O (| Vp ) מסקנה : סיבוביות זמן הריצה של האלגוריתם הנדון היא . 0 (| Vp ) האלגוריתם של פלויד-וורשל ( Floyd-Warshall ) למציאת מסלולים קצרים בין כל הזוגות נתון גרף מכוון G- { V , E ) עם פונקציית משקל . W-. E- ^ R כלומר , לכל קשת מתאימים משקל . להלן מספר דרישות לצורך ביצוע האלגוריתם ו א . הגרף G מיוצג בעזרת מטריצת סמיכות , («??) אשר מוגדרת באופן הבא :
|
|