الگوریتم Bellman–Ford
Bellman–Ford AlgorithmBellman–Ford کوتاه‌ترین مسیر از یک مبدأ را حتی با edgeهای وزن منفی پیدا می‌کند و می‌تواند negative cycle قابل‌دسترسی را تشخیص دهد.
اول این مفهوم را در ذهن نگه دار
Bellman–Ford کوتاه‌ترین مسیر از یک مبدأ را حتی با edgeهای وزن منفی پیدا می‌کند و می‌تواند negative cycle قابل‌دسترسی را تشخیص دهد.
چطور کار می‌کند؟ ساده و مرحله‌ای
همه edgeها را V−1 بار relax می‌کنیم چون یک shortest path ساده حداکثر V−1 edge دارد.
اگر در دور بعدی هنوز relaxation موفق باشد، negative cycle قابل‌دسترسی وجود دارد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم Bellman–Ford هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function bellmanFord(vertices, edges, start) {
const dist = Array(vertices).fill(Infinity);
dist[start] = 0;
for (let i = 1; i < vertices; i++) {
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
return dist;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(VE)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
با Dijkstra مقایسه کن: Bellman–Ford کندتر و O(VE) است ولی وزن منفی و تشخیص negative cycle را پشتیبانی می‌کند.
الگوریتم Bellman–Ford چه مسئله‌ای را حل می‌کند؟
Bellman–Ford کوتاه‌ترین مسیر از یک مبدأ را حتی با edgeهای وزن منفی پیدا می‌کند و می‌تواند negative cycle قابل‌دسترسی را تشخیص دهد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(VE) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.