אלגוריתם דייקסטרה – אלגוריתמים בגרפים

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

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

תעודה בסיום

• 9
• 3
• 1
• 55

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

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

תעודה בסיום

• 9
• 3
• 1
• 54

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

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

תעודה בסיום

• 9
• 3
• 1
• 57

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

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

תעודה בסיום

• 9
• 3
• 1
• 54

למדו לשלוט בחיפוש לעומק תחילה, דרך יסודית לחקור גרף. בנו מבנה נתונים לחיפוש שכנויות, כתבו DFS איטרטיבי בשפת התכנות לבחירתכם, נתחו את סיבוכיות O(V + E) והשתמשו בו כדי לספור רכיבים קשירים ולמדוד אותם.

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

תעודה בסיום

• 9
• 3
• 1
• 54