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

כל האלגוריתמים (שאותם נלמד) למציאת מסלולים זולים לכלל הזוגות מתבססים על אותו הרעיון.

1. ראשית, מניחים שהקלט של הבעיה מתאר את הבעיה בצורה נוחה (לעיתים יש צורך בהוספת עוד קשתות לגרף. מסלולים זולים לכלל הזוגות עוסק בכך).
2. כעת עובדים בשיטת הפרד ומשול - מוצאים את פתרונן של בעיות "גדולות" יותר בעזרת פתרונן של בעיות "קטנות" יותר. השאלה היא כיצד מגדירים מהן בעיות "קטנות" ו"גדולות":
   • באלגוריתם "הכפלת מטריצות" נראה שיטה לפיה פותרים בעיות קטנות יותר, בהן המסלול הזול ביותר מוגבל באורך.
   • באלגוריתם Floyd-Warshall נראה שיטה לפיה פותרים בעיות קטנות יותר, בהן המסלול הזול ביותר מוגבל בקבוצות צמתי הביניים של המסלול.