מבוא

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

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

גרף משוקלל נתון כ-n (קודקודים 0 עד n - 1) וכ-edges, מערך שטוח של שלשות [u0, v0, w0, u1, v1, w1, ...], כאשר כל שלשה מייצגת קשת מכוונת u -> v במשקל w.

בואו נתחיל!