الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm) :
📌 معرفی
الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm) یک الگوریتم برنامه ریزی پویا برای یافتن کوتاه ترین مسیر بین همه جفت گره ها در یک گراف است. این الگوریتم می تواند با وزن های منفی کار کند، اما نباید دور منفی وجود داشته باشد. ایده اصلی آن بررسی این است که آیا عبور از یک گره میانی می تواند مسیر بین دو گره را کوتاه تر کند یا خیر.
📐 مراحل الگوریتم
یک ماتریس
\[ dist \]به ابعاد
\[ V \times V \]ایجاد کن که
\[ dist[i][j] \]فاصله کوتاه ترین مسیر از i به j باشد. ابتدا
\[ dist[i][j] \]را با وزن یال مستقیم (یا بینهایت اگر یال وجود ندارد) و
\[ dist[i][i] \]را با صفر مقداردهی کن.
برای k از ۱ تا V: برای i از ۱ تا V: برای j از ۱ تا V: اگر
\[ dist[i][k] + dist[k][j] < dist[i][j] \]:
\[ dist[i][j] = dist[i][k] + dist[k][j] \]🔧 پیچیدگی
پیچیدگی زمانی الگوریتم
\[ O(V^3) \]است. این الگوریتم برای گراف های با اندازه متوسط مناسب است.
