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

בהרצאה ראינו שני אלגוריתמים למציאת מחירי המסלולים הזולים לכלל הזוגות: אלגוריתם "הכפלת מטריצות" ואלגוריתם Floyd-Warshall. כעת רוצים להיות מסוגלים גם לענות על השאלה מה צמתי המסלול הזול ביותר מכל $\displaystyle u$ לכל $\displaystyle v$. אנא שנה את האלגוריתם כך שיחזיר זוג (Min-Costs, Min-Cost-Paths) (עליך להחליט בעצמך מאיזה סוג טיפוס הוא Min-Cost-Paths). אנא עשה זאת בצורה שלא תפגע בסיבוכיות האלגוריתם. אנא כתוב גם פונקציה Cheapest-Path(Min-Costs-Path, u, v) המקבלת את הערך המוחזר ושני צמתים, ומדפיסה בסיבוכיות \Theta( במקרה הגרוע את צמתי המסלול הקצר ביותר בין שני הצמתים.

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