ראשי > מסלולים קצרים > האלגוריתם של בלמן-פורד

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

מבוא

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

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

פסאודו קוד

1. INITIALIZE-ESTIMATES (G,s)
2. for i =1 to V-1
3. ___for each edge (u,v) in G
4.___ ___Improve (u,v)
5. for each edge (u,v) in G
6. ___if d(v) > d(u) + w(u,v) then
7. ______return FALSE
8. return TRUE

הסבר :
לאחר ביצוע האיתחול הרגיל, האלגוריתם מבצע V-1 מעברים על קשתות הגרף. כל מעבר הוא איטרציה אחת של ביצוע הקלה לכל קשתות הגרף (שורות 2-4).
לאחר V-1 המעברים, מתבצעת בדיקה עם קיים מעגל שלילי בגרף (שורות 5-8) והחזרת ערך בוליאני מתאים.

דוגמת הרצה

ניתוח סיבוכיות

האיתחול הבסיסי של האלגוריתם התמצע ב (O(V, כל אחד מ V-1 המעברים של הקלה על כל הקשתות מתבצע ב (O(E.
בדיקת קיום המעגל השלילי מתבצעת ב (O(E.
לכן זמן ריצתו הכולל של אלגוריתם בלמן-פורד הוא (O(VE.