الگوریتم فورد-بلمن
اجازه دهید یک نمودار وزنی جهت دار G با راس n و یال های m و مقداری راس شروع v لازم است طول کوتاهترین مسیرها از راس v تا همه رئوس دیگر را پیدا کنید.
مانند Dijkstra، Ford-Bellman به دنبال فاصله از راس 1 تا سایر موارد است، اما با لبه های منفی کار می کند.
الگوریتم فورد-بلمن خود از چند مرحله تشکیل شده است (
n-1). در هر مرحله، تمام لبه‌های نمودار بررسی می‌شوند و الگوریتم سعی می‌کند در امتداد هر یال
(a, b) هزینه
c آرام شود.
آرامش در امتداد لبه — این تلاشی است برای بهبود معنای
d[a] مقدار
d[b] + c. در واقع این بدان معناست که ما سعی داریم با استفاده از edge و پاسخ فعلی برای بالا.
آرایه
d آرایه‌ای از کوتاهترین طول‌ها از راس شروع است، درست مانند Dijkstra، در ابتدا آن را با حداکثر تعداد ممکن پر می‌کنیم، به جز راس شروع، که باید در آن قرار دهید. 0.
برای ذخیره یال‌ها، از ماتریس مجاورت یا ماتریس وزن استفاده نمی‌شود، بلکه از فهرستی استفاده می‌شود که نشان می‌دهد لبه از کدام گره خارج می‌شود (
from)، که به آن می‌آید (
to) و وزن آن (هزینه).
لبه ساختار {
int from, to, cost;
};
بردار<لبه> لبه ها؛
ثابت INF نشان دهنده عدد "بی نهایت" است. - باید به گونه ای انتخاب شود که آشکارا از تمام طول مسیرهای ممکن تجاوز کند.
ساده ترین پیاده سازی الگوریتم:
d[v] = 0;
برای (int i=0; i<n-1; ++i)
برای (int j=0; j<m; ++j)
if (d[ لبه‌ها[j].from] <INF)
d[لبه[j].to] = min(d[لبه[j].to], d[لبه[j].from] + یال[j].cost);
یا کمی کوتاهتر با استفاده از نحو
C++11:
d[v] = 0;
برای (int i=0; i< n-1; ++i)
برای (لبه j: لبه ها)
اگر (d[j.from] <INF)
d[j.to] = min(d[j.to], d[j.from] + j.cost);
نمونه کار
یک نمودار جهت دار ساده بگیرید با 5 گره، 4 یال با وزن برابر 1.
بیایید لیستی از لبه ها را به ترتیب معرفی کنیم.
4 5 1
3 4 1
2 3 1
1 2 1
مقادیر اولیه در آرایه های کوتاه ترین طول ها:
که در آن inf باید یک عدد صحیح منطبق باشد که همیشه از وزن یال بزرگتر است.
پس از اولین پاس
بعد از پاس 2
بعد از پاس سوم
بعد از پاس چهارم
اگر لبه‌ها را به ترتیب از 1 تا آخر تغذیه کنیم، می‌توانیم کوتاهترین طول‌ها را پس از پاس اول پیدا کنیم.