|
|
עמוד:229
5 , 4 מסלולים אופטימליים ברשת מקדקוד המקור ליתר הקדקודים - אלגוריתם דיקסטרה ישנן מספר שיטות ( אלגוריתמים , ( למציאת מסלולים אופטימליים ברשת מקדקוד המקור ליתר הקדקודים . בסעיף הזה נציג את אלגוריתם דיקסטרה . ( Dijkstra ) נתונה הרשת G = ( V , E ) עם פונקציית המשקל , W : E ^> R + כלומר , לכל קשת מתאימים משקל חיובי . ? להלן מספר הנחות והגדרות לצורך הפעלת האלגוריתם א . נניח שהגרף מיוצג בעזרת מטריצת סמיכות וכדלקמן ו המטריצה A מייצגת את אורך המסלול המינימלי הזמני מהקדקוד ו לקדקוד J הבעיה הנדונה היא בעיית תכנון ליניארי בשלמים . בסעיף הבא נתמקד באלגוריתם שבעזרתו נמצא מסלולים אופטימליים מקדקוד המקור לכל קדקוד אחר ברשת .
|
|