|
|
עמוד:243
צעד 2 עדיין כל קדקוד מוכנס לקבוצה P בדיוק פעם אחת . לפיכך , כל קשת ברשימת הסמיכות נבחנת בדיוק פעם אחת במהלך האלגוריתם . כאמור , מספרן הכולל של הקשתות ברשימת הסמיכות הוא . 0 (| £ |) לכן צעד 2 מתבצע 0 (\ E \) פעמים , ובכל צעד נדרש זמן . O ( log )| V |) מכאן , זמן הריצה של צעד 2 הוא . O (| £ | log )| V |) מסקנה : זמן הריצה של האלגוריתם כולו הוא : 0 (| EllogM ) + MlogM ) = 0 (( q + M ) log | l 1 ) בגרף קשיר מאחר , | £ | > | V | -w סיבוביות זמן הריצה של האלגוריתם דיקסטרה היא : . O (| £ |)| log | V |) 5 . 4 . 1 שאלות לסיכום סעיף 5 . 4 שאלה 5 . 8 נתונה הרשת הזאת : הניחו כי קדקוד המקור הוא . 1 א . הריצו את האלגוריתם של דיקסטרה על הרשת הנתונה . ב . מצאו מסלול מינימלי מקדקוד המקור ליתר הקדקודים ברשת הזאת . שאלה 5 . 9 נתונה הרשת הזאת :
|
|