אלגוריתם בלמן-פורד – אלגוריתמים על גרפים

למדו לעומק את אלגוריתם דייקסטרה, שיטה חמדנית למציאת המסלולים הקצרים ביותר ממקור יחיד בגרפים עם משקלים שאינם שליליים. קראו קשתות משוקללות, בנו בשפת התכנות לבחירתכם את חישוב המרחקים המלא, וענו על שאילתות לגבי מסלולים בין זוגות צמתים ולגבי הצומת הרחוק ביותר.

אלגוריתמים על גרפים

תעודה בסיום

• 9
• 3
• 1
• 54

שלטו באלגוריתם של פרים למציאת עצים פורשים מינימליים: בנו עץ אחד מקודקוד התחלתי, והוסיפו בכל פעם את הקשת החוצה הזולה ביותר. ממשו אותו בשפת התכנות לבחירתכם וענו על שאילתות לגבי קשתות צוואר בקבוק וקישוריות — האלגוריתם המקביל לאלגוריתם של קרוסקל.

אלגוריתמים על גרפים

תעודה בסיום

• 9
• 3
• 1
• 55

שלטו בחיפוש לרוחב, שיטת מעבר על גרף שכבה אחר שכבה שעומדת בבסיס מציאת מסלולים קצרים ביותר. בנו מבנה לאיתור שכנים, כתבו אלגוריתם חיפוש לרוחב איטרטיבי שמשתמש בתור בשפת התכנות לבחירתכם, והשתמשו בו כדי למצוא את המרחקים של המסלולים הקצרים ביותר בגרפים לא משוקללים.

אלגוריתמים על גרפים

תעודה בסיום

• 9
• 3
• 1
• 54

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

אלגוריתמים על גרפים

תעודה בסיום

• 9
• 3
• 1
• 55

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

אלגוריתמים על גרפים

תעודה בסיום

• 9
• 3
• 1
• 57