|
|
עמוד:317
הערות : . 1 באלגוריתם של פלויד-וורשל ניתן לגלות אם בגרף המכוון קייס מעגל שלילי על פי התנאי הזה . י ברשת קיים מעגל בעל משקל שלילי אם ורק אם 0 0 < 0 עבור 1 כלשהו 1-מ עד / 1 ועבור m כלשהו 1-מ עד n nwn ) מדוע (! . 2 אם ברשת אין מעגל בעל משקל שלילי , אז בעזרת האלגוריתם של פלויד-וורשל ניתן למצוא את המעגל בעל המשקל הקטן ביותר לפי הביטוי הזה : 5 . 8 . 1 שאלות לסיכום סעיף 5 . 8 שאלול 5 . 30 נתונה הרשת שלהלן : המספרים על גב הקשתות מבטאים את אורכי הקשתות . הניחו כי צומת המקור היא . 1 הריצו את אלגוריתם דיקסטרה על הרשת הנתונה . מצאו מסלול מינימלי מצומת המקור 1 ליתר הצמתים ברשת זו . שאלה 5 . 31 א . הציגו דוגמה שמראה שהאלגוריתם דיקסטרה שוגה על גרף עם משקלות שליליים . ( הגרף אינו צריך להכיל מעגל שלילי ( . ב . הסבירו מדוע הוכחת האלגוריתם אינה תקפה במקרה הזה .
|
|