Bellman-Ford کوتاهترین مسیر تکمبدأ را با پشتیبانی از وزن منفی پیدا میکند و چرخه منفی را هم تشخیص میدهد. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Bellman-Ford زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
تمام یالها را بارها Relax میکنیم تا فاصلهها دیگر بهتر نشوند.
مراحل اجرا
- فاصله مبدأ صفر و بقیه Infinity.
- تمام یالها را V-1 بار Relax میکنیم.
- اگر مسیر جدید کوتاهتر بود dist را آپدیت میکنیم.
- یک دور اضافه برای تشخیص negative cycle اجرا میکنیم.
نمونه کد JavaScript
function bellmanFord(vertices, edges, source) {
const dist = Object.fromEntries(vertices.map(v => [v, Infinity]));
dist[source] = 0;
for (let i = 0; i < vertices.length - 1; i++)
for (const [u,v,w] of edges)
if (dist[u] !== Infinity && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
for (const [u,v,w] of edges)
if (dist[u] !== Infinity && dist[u] + w < dist[v])
throw new Error("Negative cycle");
return dist;
}مثالهای واقعی و دنیای کار
- مدلهای سود/زیان
- Distance Vector Routing
- Credit/Penalty Graph
- تشخیص Negative Cycle
پیچیدگی زمانی و فضایی
O(VE) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
وجود وزن منفی یا نیاز به تشخیص چرخه منفی
چه زمانی مناسب نیست؟
با وزنهای غیرمنفی Dijkstra معمولاً سریعتر است.
جمعبندی
Bellman-Ford را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.