|
|
עמוד:241
אך בעזרת אלגוריתם דיקסטרה , לאחר שתי האיטרציות הראשונות נקבל את תמונת המצב שלהלן ( בדקו (! באיטרציה הבאה ( מבין הקדקודיס הומניים ( C , D נבחר בקדקוד , D כיוון ש ו 4 C ] = 15 > ] = 12 לפיכך , הקבוצה P תהיה : P = { A . B , D \ כלומר , אוון המסלול המינימלי ( לפי האלגוריתם של דיקסטרה ) מקדקוד המקור A לקדקוד D הוא . 12 מאחר שהקדקוד D מצטרף לקבוצה , ? אורך המסלול המינימלי מהקדקוד A לקדקוד D הוא קבוע , וערכו לא ישתנה עד סוף האלגוריתם . ברור שהתוצאה שקיבלנו d [ D ] = 12 : אינה נכונה , כיוון שערכו הצפוי של d [ D ] הוא . 8 זה סותר את הנחתנו . מסקנה : האלגוריתם של דיקסטרה , מתאים רק לרשתות שבהן המשקלות על הקשתות חיוביים . ניתוח היעילות של האלגוריתם של דיקסטרה נתון הגרף . G = ( V , E ) \ V \ מציין את מספר הקדקודים בגרף G אתחול : צעד 0 0 . 1 דורש זמן של 0 (| v |) 0 . 2 דורש זמן של 0 (\\\) 0 . 3 דורש זמן של 0 ( 1 ^ 1 ) 0 . 5 דורש זמן של 0 ( 11 |) 0 . 6 דורש זמן של O (\ V \) לכן , סיבוביות זמן הריצה של צעד 0 היא ? 0 {\ v \)
|
|