Floyd-Warshall با Dynamic Programming فاصله کوتاهترین مسیر بین تمام جفت رأسها را محاسبه میکند. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Floyd-Warshall زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
برای هر رأس k بررسی میکنیم آیا عبور از k مسیر i تا j را کوتاهتر میکند.
مراحل اجرا
- ماتریس فاصله را مقداردهی میکنیم.
- قطر اصلی صفر است.
- برای هر k، i و j رابطه min را اعمال میکنیم.
- ماتریس نهایی شامل فاصله همه جفتهاست.
نمونه کد JavaScript
function floydWarshall(matrix) {
const d = matrix.map(r => [...r]), n = d.length;
for (let k=0;k<n;k++) for (let i=0;i<n;i++) for (let j=0;j<n;j++)
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
return d;
}مثالهای واقعی و دنیای کار
- فاصله بین همه شعب
- Routing Matrix
- Reachability
- پیشمحاسبه مسیر Logistics
پیچیدگی زمانی و فضایی
O(V³) زمان و O(V²) حافظه
چه زمانی استفاده کنیم؟
نیاز به all-pairs shortest paths با V متوسط
چه زمانی مناسب نیست؟
برای گراف بسیار بزرگ sparse معمولاً مناسب نیست.
جمعبندی
Floyd-Warshall را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.