לפניכם גרף ממושקל G₁:

(1) איזה אלגוריתם מחזיר את המסלול הקצר (הקל) בין שני קודקודים בגרף ממושקל (אי־שלילי) כלשהו?

מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו את תשובתכם.

נוסף על כך, הריצו את האלגוריתם שכתבתם, בעבור הגרף הנתון G₁, מצומת S לצומת T. בצעו מעקב שלב אחר שלב ורשמו את המסלול ואת אורכו (סכום משקליו).

(2) עבור גרף G ממושקל כלשהו, הרצנו את האלגוריתם המוצא את המסלול הקצר (הקל) בין שני קודקודים, וקיבלנו מסלול העובר דרך הקשתות E(e_i, e_j, e_m, ...).

• האם המסלול הקצר בין שני הקודקודים יישאר בהכרח זהה אם משקל כל אחת מן הקשתות בגרף יוכפל ב־x (1 < x)? נמקו את תשובתכם.
• האם המסלול הקצר בין שני הקודקודים יישאר בהכרח זהה אם משקל כל אחת מן הקשתות בגרף יגדל ב־x (1 < x)? נמקו את תשובתכם.

לפניכם גרף מכוון G:

(1) הציגו שתי סריקות DFS מקודקוד התחלה a כך שיתקבלו שני עצים שהגבהים שלהם שונים זה מזה.

(2) הוסיפו מספר מינימלי של קשתות כך שבשלוש סריקות DFS מקודקוד a, יתקבלו שלושה עצים שהגבהים שלהם שונים זה מזה. סרטטו את הגרף לאחר ההוספה, והציגו את שלוש הסריקות.