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

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

העיקרון המרכזי הוא "הקלה" (Relaxation), בדיקה ועדכון של המרחקים אם ניתן לשפרם. לכל צומת v שומרים d[v], המרחק הקצר שנמצא עד כה מהמקור s אל v. בתחילת הריצה d[s]=0 ולשאר הצמתים נותנים אינסוף (כלומר עדיין לא נמצא מסלול). בנוסף שומרים מצביע ל"הצומת הקודם" במסלול, כדי לבנות את המסלול לאחר מכן.

בעת הקלה על קשת (u→v) בודקים אם d[v] > d[u] + w(u,v). אם כן, מעדכנים את d[v] ל־d[u]+w(u,v) ואת "הקודם" של v ל־u. אלגוריתם בלמן-פורד מבצע |V|-1 איטרציות, ובכל איטרציה עושה הקלה על כל הקשתות. כל איטרציה משפרת את המרחקים, ולבסוף מקבלים את המסלולים הקצרים ביותר בתנאי שאין מעגלים שליליים. בסיום מריצים מעבר נוסף על כל הקשתות כדי לבדוק אם אפשר עדיין להקטין מרחק; אם כן יש מעגל שלילי.

הגרסה הפורמלית מאתחלת את כל v.distance ל־infinity וחוסנת את source.distance ל־0. אז מריצים לולאה |V|-1 פעמים: בכל איטרציה עוברים על כל הקשתות ועושים את בדיקת ההקלה ועדכון המרחק והקודם. לאחר מכן עוברים שוב על כל הקשתות כדי לבדוק אם קיים עדכון אפשרי נוסף; עדכון כזה מצביע על מעגל בעל משקל שלילי.

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

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

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

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

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