סטודנט לא רשע מספיק השתלט על קניגסברג, וכלא 4 משגיחים שעשו יותר מדי רעש במבחן. הוא שכר סטודנטים ממדויקים לשמור על הגשרים. ניתן לשחד כל סטודנט ע"י מספר שונה של כוסות קפה והוא יפיל את המשגיח למים. יש לך 6 שקלים לקפה אמון, האם תצליח להפיל את כולם?
השאלות האמיתיות:
1. בלמן פורד לא מכוון - אי אפשר אם יש קשת שלילית לא מכוונת - למשל קשת (u,v) שלילית תיתן מעגל שלילי (u,v)->(v,u)
2. דייקסטרה לא מכוון - בדפים עם האלגוריתמים רשום "מכוון או לא מכוון", במצגת מהתרגול רשום "האלגוריתם של דייקסטרה רץ על גרף מכוון" וכיוונו כל קשת לשני הכיוונים.
מה זה משנה? אם אני ב"פסאודו" אז כשאני אוציא קודקוד אני אבחן את כל הקשתות שלו, אם אני ברשימת שכנויות גם ככה כל קשת מופיעה "פעמיים".
3. דוגמא של מיכה - "דיאגרמות PERT", כל שלב יכול להתבצע אחרי שהשלבים הקודמים שתלוי בהם מסתיימים.
עשינו גרף מכוון שהצמתים הם השלבים והקשתות הן התלויות בין השלבים (קשת יוצאת מדרישת קדם למה שרוצים לבצע)
המשקל של הקשת זה הזמן שלאחר שהדרישת קדם הסתיימה אפשר לבצע, מניחים שאין מעגלים (הנחנו גם בדוגמא שעשינו שמכל קודקוד אפשר להגיע לקודקודים ה"באים אחריו")
ומחפשים את הזמן המינימלי שבו כל השלבים יתבצעו.
הפתרון היה לחשב מסלול במשקל מקסימלי מצומת ההתחלה לצומת הסיום (אותם מוצאים ע"י מיון טופולוגי)
להעביר את כל המשקלים לשליליים ואז להריץ דייקסטרה
ההגיון ברור, הרי המסלול הקצר מהראשון לאחרון יכסה את הזמן של כל הקודקודים האחרים, מכיוון שהמשקלים שליליים לוקחים יותר זמן לכן כל המסלולים המקבילים שלוקחים פחות זמן מתבצעים גם,
אבל זה מרגיש קצת "נפנוף" לא דיברנו על זה יותר מדי:
1. בהוכחה של דייקסטרה משתמשים בזה שתת-מק"ב משקלו קטן שווה למשקל המק"ב וכאן זה לא מתקיים
2. בעקרון בלי כל מיני תנאים, למצוא מסלול במשקל מקסימלי זה לא פתיר בזמן טוב אם אני זוכר נכון (פולינומיאלי)
3. מה לגבי אפסים אם יש?