מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/מסלולים זולים לכלל הזוגות/תרגילים/ווריאציה עם מחירים שליליים/שאלה

השאלה הבאה מתייחסת לכל אחד מהאלגוריתמים למסלולים זולים לכלל הזוגות שלמדנו (אלגוריתם "הכפלת מטריצות" ואלגוריתם Floyd-Warshall).

שימו לב: הטענות עבור שני האלגוריתמים דומות מאד זו לזו. אנא בחר אלגוריתם אחד מהשניים, ענה על השאלה לגביו, ורק וודא שהנך יודע לפתור את השני.

1. אנא הוכח שכאשר יש בגרף מעגלים בעלי משקל שלילי (כלומר מעגל שסכום קשתותיו שלילי), אז בהכרח קיימים שני צמתים, $\displaystyle u$ ו$\displaystyle v$, כך שאין מסלול סופי זול ביותר מ$\displaystyle u$ ל$\displaystyle v$.
2. האלגוריתמים שראינו אכן מוצאים תמיד מסלול סופי. אנא הסבר היכן הוכחת הנכונות מניחה במובלע שאין מעגלים בעלי משקל שלילי.
3. אנא הוכח שכאשר אין מעגלים בעלי משקל שלילי, אז בלי קשר לסימן משקל הקשתות, האלגוריתמים אכן עובדים.