الگوریتم Floyd–Warshall
Floyd–Warshall AlgorithmFloyd–Warshall با Dynamic Programming کوتاه‌ترین مسیر بین تمام جفت Nodeها را محاسبه می‌کند و مرحله‌به‌مرحله Nodeهای میانی مجاز را اضافه می‌کند.
اول این مفهوم را در ذهن نگه دار
Floyd–Warshall با Dynamic Programming کوتاه‌ترین مسیر بین تمام جفت Nodeها را محاسبه می‌کند و مرحله‌به‌مرحله Nodeهای میانی مجاز را اضافه می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای هر k بررسی می‌کنیم آیا مسیر i→k→j از dist[i][j] بهتر است یا نه.
سه loop تو در تو زمان O(V³) و ماتریس فاصله حافظه O(V²) می‌دهد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم Floyd–Warshall هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
O(V³)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
برای All-Pairs Shortest Path با V متوسط مناسب است؛ برای گراف بسیار بزرگ و sparse معمولاً انتخاب اول نیست.
الگوریتم Floyd–Warshall چه مسئله‌ای را حل می‌کند؟
Floyd–Warshall با Dynamic Programming کوتاه‌ترین مسیر بین تمام جفت Nodeها را محاسبه می‌کند و مرحله‌به‌مرحله Nodeهای میانی مجاز را اضافه می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(V³) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.