מבוא

ברוכים השבים לסדרת אלגוריתמים על גרפים! דייקסטרה מהיר, אבל הוא לא עובד כשקשתות יכולות להיות שליליות. בלמן-פורד מטפל במשקלים שליליים, והוא אפילו יכול לומר לכם מתי יש בגרף מעגל שלילי.

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

קודקודים שאינם נגישים מדווחים כ--1. בואו נתחיל!