در این مقاله درمورد الگوریتم فلوید وارشال و نحوه کارکرد آن، و همچنین پیاده سازی در زبان‌های مختلف صحبت کرده‌ایم. روند کار این الگوریتم به این صورت است که با شروع از گراف اولیه، به تدریج و با بررسی تمامی جفت‌های رأس‌ها، مسیرهای کوتاه‌تر را از طریق دیگر رأس‌ها پیدا می‌کند. در ادامه توضیحات بیشتری آورده شده است.
مقدمه
الگوریتم فلوید وارشال یکی از مهم‌ترین و پرکاربردترین الگوریتم‌ها در نظریه گراف‌ها و حل مسائل مسیریابی است. این الگوریتم به‌ویژه در مواقعی که نیاز به یافتن کوتاه‌ترین مسیر بین تمام جفت‌گره‌های یک گراف وجود دارد، کارایی بالایی دارد. برخلاف بسیاری از الگوریتم‌های دیگر که تنها کوتاه‌ترین مسیر از یک گره به گره دیگر را محاسبه می‌کنند، فلوید وارشال قادر است در یک بار اجرای الگوریتم، کوتاه‌ترین مسیرها را بین تمام جفت‌گره‌ها پیدا کند. این ویژگی باعث می‌شود که در مسائل متنوعی همچون مسیریابی شبکه‌ها، تحلیل سیستم حمل‌ونقل، سامانه GIS و رباتیک کاربرد داشته باشد. در ادامه، به توضیح دقیق‌تر الگوریتم فلوید وارشال و نحوه عملکرد آن می‌پردازیم.
الگوریتم فلوید وارشال چیست؟
الگوریتم فلوید وارشال یک روش مبتنی بر برنامه‌نویسی پویا در علوم کامپیوتر است که برای حل مسئله کوتاه‌ترین مسیر بین همه جفت‌گره‌ها در یک گراف استفاده می‌شود. این الگوریتم با استفاده از یک ماتریس فاصله، مسیرهای کوتاه‌تر را به‌طور پیوسته به‌روزرسانی می‌کند. هر بار که یک گره جدید به عنوان گره میانی در نظر گرفته می‌شود، ماتریس فاصله‌ها با استفاده از این گره به‌روز می‌شود و مسیرهای کوتاه‌تر محاسبه می‌شوند. الگوریتم فلوید وارشال، برخلاف الگوریتم‌های حریصانه مانند الگوریتم دایکسترا، قادر است به‌طور همزمان تمام مسیرهای کوتاه بین جفت‌گره‌ها را محاسبه کند و به همین دلیل در بسیاری از مسائل کاربرد دارد.
یکی از ویژگی‌های برجسته الگوریتم فلوید وارشال این است که می‌تواند با گراف‌هایی که دارای وزن‌های منفی بر روی یال‌ها هستند نیز کار کند. البته لازم به ذکر است که این الگوریتم برای گراف‌هایی با چرخه‌های منفی مناسب نیست و ممکن است نتایج اشتباهی تولید کند. همچنین پیچیدگی زمانی این الگوریتم به‌طور کلی به صورت (n۳)O است که به معنای افزایش قابل توجه زمان اجرای آن برای گراف‌های بزرگ است. با این حال، این الگوریتم به دلیل سادگی پیاده‌سازی و توانایی انجام محاسبات در یک اجرا، در بسیاری از کاربردهای عملی مورد استفاده قرار می‌گیرد.
تاریخچه الگوریتم
الگوریتم فلوید وارشال ابتدا توسط ریچارد فلوید در سال ۱۹۶۲ طراحی شد. فلوید این الگوریتم را به‌عنوان راه‌حلی برای مسائلی که نیاز به یافتن کوتاه‌ترین مسیر بین همه جفت‌گره‌ها داشتند، ارائه کرد. او این الگوریتم را به‌عنوان یک روش برنامه‌نویسی پویا معرفی کرد که می‌توانست با استفاده از یک ماتریس فاصله، به‌طور موثر مسیرهای کوتاه را پیدا کند. فلوید توانست با ارائه این الگوریتم، انقلابی در نحوه‌ی محاسبه مسیرهای کوتاه در گراف‌ها ایجاد کند و این الگوریتم به یکی از مباحث مهم در نظریه گراف‌ها تبدیل شد.
استیفن وارشال، که همکار فلوید در این تحقیقات بود، به توسعه و تکمیل الگوریتم کمک کرد. او اصلاحات و بهبودهایی در الگوریتم فلوید ایجاد کرد که به‌ویژه در زمینه کار با گراف‌های جهت‌دار و بدون جهت و همچنین در استفاده از وزن‌های منفی بر روی یال‌ها اهمیت داشت. این همکاری بین فلوید و وارشال باعث شد تا الگوریتم به ابزاری قدرتمند و شناخته‌شده در علوم کامپیوتر و ریاضیات تبدیل شود و همچنان در بسیاری از کاربردها به‌عنوان یکی از بهترین روش‌ها برای حل مسئله کوتاه‌ترین مسیر استفاده شود.
تفاوت الگوریتم فلوید وارشال با سایر الگوریتم‌های کوتاه‌ترین مسیر
الگوریتم فلوید وارشال با سایر الگوریتم‌های کوتاه‌ترین مسیر مانند دایکسترا و بلمن‌فورد تفاوت‌های قابل توجهی دارد. برخلاف دایکسترا که تنها کوتاه‌ترین مسیر از یک گره خاص به دیگر گره‌ها را پیدا می‌کند و نیاز به اجرای مجدد برای هر گره‌ی مبدا دارد، فلوید وارشال قادر است در یک اجرای واحد، کوتاه‌ترین مسیر بین تمام جفت‌گره‌ها را محاسبه کند.
همچنین برخلاف بلمن‌فورد که برای گراف‌های با وزن منفی مناسب است اما فقط برای یافتن کوتاه‌ترین مسیر از یک گره به دیگر گره‌ها عمل می‌کند، فلوید وارشال به‌طور همزمان از تمام گره‌ها به عنوان گره‌های میانی برای به‌روزرسانی مسیرها استفاده می‌کند و می‌تواند به‌طور کلی برای گراف‌هایی با وزن منفی بدون چرخه منفی مفید باشد. در نتیجه، فلوید وارشال برای مسائل All-Pairs Shortest Path (APSP) که نیاز به محاسبه کوتاه‌ترین مسیر بین تمامی جفت‌گره‌ها دارند، انتخاب بهتری است، در حالی که دایکسترا و بلمن‌فورد بیشتر برای محاسبه مسیرهای کوتاه از یک گره به گره دیگر استفاده می‌شوند.
معرفی مسئله کوتاه‌ترین مسیر
مسئله کوتاه‌ترین مسیر یکی از مسائل بنیادین در نظریه گراف‌ها است که هدف آن پیدا کردن مسیر با کمترین هزینه بین دو گره خاص در یک گراف وزن‌دار است. این هزینه می‌تواند نمایانگر مسافت، زمان یا هر نوع هزینه دیگری باشد که برای حرکت از یک گره به گره دیگر صرف می‌شود. در بسیاری از کاربردها مانند مسیریابی شبکه، حمل‌ونقل و برنامه‌ریزی حرکت ربات‌ها، حل این مسئله از اهمیت زیادی برخوردار است.
در گراف‌های بزرگ، یافتن کوتاه‌ترین مسیر از یک گره به تمامی گره‌های دیگر یا پیدا کردن کوتاه‌ترین مسیر بین تمام جفت‌گره‌ها می‌تواند به یک چالش پیچیده تبدیل شود. الگوریتم‌های مختلفی برای حل این مسئله وجود دارند که هر کدام ویژگی‌ها و محدودیت‌های خاص خود را دارند. یکی از این الگوریتم‌ها، الگوریتم فلوید وارشال است که قادر است کوتاه‌ترین مسیرها را بین همه جفت‌گره‌ها در یک اجرا محاسبه کند.
تعریف گراف وزن‌دار
گراف وزن‌دار یک ساختار ریاضی است که از مجموعه‌ای از گره‌ها (رأس‌ها) و یال‌ها (اتصالات بین گره‌ها) تشکیل می‌شود. هر یال در این گراف دارای یک وزن است که معمولاً نمایانگر هزینه، زمان، مسافت یا هر ویژگی دیگر بین دو گره است. در گراف‌های وزن‌دار، این وزن‌ها می‌توانند مثبت، منفی یا حتی صفر باشند. این ویژگی باعث می‌شود که گراف‌های وزن‌دار ابزاری مناسب برای مدل‌سازی بسیاری از مسائل دنیای واقعی مانند شبکه‌های حمل‌ونقل یا مسیریابی در اینترنت باشند.
گراف‌های وزن‌دار می‌توانند به صورت جهت‌دار یا بدون جهت باشند. در گراف‌های جهت‌دار، یال‌ها یک جهت مشخص دارند و مسیر از یک گره به گره دیگر ممکن است با مسیر معکوس متفاوت باشد. در گراف‌های بدون جهت، یال‌ها فاقد جهت هستند و مسیر از یک گره به گره دیگر معکوس‌پذیر است. در هر دو حالت، وزن یال‌ها نقش حیاتی در تعیین هزینه یا زمان برای حرکت از یک گره به گره دیگر ایفا می‌کند.
مسئله کوتاه‌ترین مسیر بین همه جفت‌گره‌ها
مسئله “کوتاه‌ترین مسیر بین همه جفت‌گره‌ها” (All-Pairs Shortest Path) به این صورت تعریف می‌شود که در یک گراف وزن‌دار، باید کوتاه‌ترین مسیر ممکن را بین هر جفت گره در گراف پیدا کرد. در این مسئله، هدف این است که مجموع وزن‌های مسیرهای مختلف بین گره‌ها به حداقل برسد. این مسئله معمولاً برای مسائلی کاربرد دارد که نیاز به یافتن سریع‌ترین یا کم‌هزینه‌ترین مسیرهای ممکن بین تمامی گره‌ها در یک گراف دارند، مانند مسیریابی در شبکه‌های کامپیوتری، برنامه‌ریزی حمل‌ونقل یا تحلیل شبکه‌های اجتماعی.
فرضیات
برای حل این مسئله با استفاده از الگوریتم فلوید وارشال، فرضیات خاصی وجود دارد:
- وجود وزن‌های منفی: الگوریتم فلوید وارشال قادر است با گراف‌هایی که دارای وزن‌های منفی در یال‌ها هستند، کار کند. این ویژگی در مقایسه با الگوریتم‌هایی مانند دایکسترا که تنها برای گراف‌های با وزن‌های مثبت مناسب است، برتری دارد.
- نبود دور منفی: یکی از پیش‌نیازهای مهم برای اجرای صحیح الگوریتم فلوید وارشال این است که گراف نباید دارای چرخه‌های منفی باشد. چرا که در صورت وجود چنین چرخه‌هایی، الگوریتم به نتیجه‌ی نادرست خواهد رسید و نمی‌تواند به درستی کوتاه‌ترین مسیرها را محاسبه کند. در این موارد، لازم است که ابتدا تشخیص داده شود که آیا گراف دارای چرخه منفی است یا خیر.
مراحل اجرای الگوریتم فلوید وارشال
ابتدا ماتریس جواب را مشابه ماتریس گراف ورودی به‌عنوان گام اول مقداردهی اولیه کنید. سپس ماتریس جواب را با در نظر گرفتن تمامی رئوس به‌عنوان رئوس میانی به‌روزرسانی کنید. ایده این است که هر رأس را یکی یکی انتخاب کرده و تمام مسیرهای کوتاه‌تری را که آن رأس را به‌عنوان رأس میانی در مسیر کوتاه انتخابی دارند، به‌روزرسانی کنید.
زمانی که رأس شماره k را به‌عنوان رأس میانی انتخاب می‌کنیم، رئوس {۰، ۱، ۲، … k-1} را قبلاً به‌عنوان رئوس میانی در نظر گرفته‌ایم.
برای هر جفت رأس (i, j) از رئوس مبدا و مقصد، دو حالت ممکن وجود دارد:
- رأس k در مسیر کوتاه از i به j رئوس میانی نیست. در این صورت، مقدار dist[i][j] را بدون تغییر نگه می‌داریم.
- رأس k در مسیر کوتاه از i به j رئوس میانی است. در این صورت، اگر dist[i][j] بزرگتر از dist[i][k] + dist[k][j] باشد، بنابراین مقدار dist[i][j] را به مقدار dist[i][k] + dist[k][j] به‌روزرسانی می‌کنیم. به عبارتی اگر:
dist[i][j] > dist[i][k] + dist[k][j]
آنگاه:
dist[i][j] = dist[i][k] + dist[k][j]
به زبان ساده اگر مسیر فعلی بین رأس i و j طولانی‌تر از مسیری باشد که از رأس i به k و سپس از k به j می‌رود، در این صورت، مقدار dist[i][j] را با جمع dist[i][k] + dist[k][j] جایگزین می‌کنیم، چون مسیر جدید کوتاه‌تر است. یعنی اگر مسیر جدید از طریق k کوتاه‌تر باشد، مقدار را جایگزین می‌کنیم.
ایده الگوریتم فلوید وارشال
فرض کنید یک گراف به صورت [][]graph داریم که شامل V رأس از ۰ تا V-1 است. حالا می‌خواهیم یک ماتریس [][]dist به دست بیاوریم که در آن dist[i][j] نشان‌دهنده کوتاه‌ترین مسیر از رأس i به رأس j است.
بیایید فرض کنیم که بین رأس‌های i و j، رأس‌های میانی نیز وجود دارند. ایده‌ی الگوریتم فلوید وارشال این است که هر رأس k از ۰ تا V-1 را به ترتیب به عنوان یک رأس میانی در نظر می‌گیریم.
وقتی رأس k را بررسی می‌کنیم، فرض بر این است که قبلاً تمام رأس‌های ۰ تا k-1 بررسی شده‌اند. بنابراین، از کوتاه‌ترین مسیرهایی که در مراحل قبل (تا رأس k-1) ساخته‌ایم استفاده می‌کنیم تا مسیرهای کوتاه‌تری بسازیم که رأس k را نیز در بر می‌گیرند.
به زبان ساده‌تر:
- مرحله به مرحله، هر رأس را به عنوان نقطه‌ی واسط در نظر می‌گیریم.
- بررسی می‌کنیم که آیا عبور از این رأس جدید باعث کوتاه‌تر شدن مسیر بین دو رأس دیگر می‌شود یا نه.
- اگر مسیر کوتاه‌تری پیدا شد، آن را به‌روزرسانی می‌کنیم.
شکل زیر، ویژگی زیرساخت بهینه (Optimal Substructure) در الگوریتم فلوید وارشال را نشان می‌دهد.
مثال برای الگوریتم فلوید وارشال
برای بررسی نحوه عملکرد الگوریتم فلوید وارشال یک گراف را در نظر بگیرید، برای مثال:
۱- ماتریس فاصله‌ها ([][]Distance) را با توجه به گراف ورودی با توجه به شکل زیر مقداردهی اولیه می‌کنیم (به‌طوری‌که Distance[i][j] برابر با وزن یال از گره i به گره j باشد):
- این مرحله برای تنظیم مقادیر اولیه استفاده می‌شود. برای هر جفت گره i و j، اگر یالی بین این دو گره وجود داشته باشد، وزن آن یال را در Distance[i][j] قرار می‌دهیم. اگر یال وجود نداشته باشد، مقدار آن را بی‌نهایت (∞) در نظر می‌گیریم تا نشان دهیم که هیچ مسیری بین این دو گره وجود ندارد.
۲- رأس A را به عنوان رأس میانی در نظر می‌گیریم. سپس برای هر جفت رأس i و j، مقدار Distance[i][j] را به‌روزرسانی می‌کنیم.
- با بررسی اینکه آیا مسیر از i به j از طریق A کوتاه‌تر از مسیر قبلی است یا خیر، در صورتی که مسیر جدید کوتاه‌تر باشد، مقدار ماتریس Distance[i][j] با فرمول زیر به‌روزرسانی و مقدار جدید جایگزین می‌شود.
Distance[i][j] = minimum (Distance[i][j], Distance[i] [A] + Distance[A][j])
۳- رأس B را به عنوان رأس میانی در نظر می‌گیریم. سپس برای هر جفت رأس i و j، مقدار Distance[i][j] را به‌روزرسانی می‌کنیم.
- با بررسی اینکه آیا مسیر از i به j از طریق B کوتاه‌تر از مسیر قبلی است یا خیر، در صورتی که مسیر جدید کوتاه‌تر باشد، مقدار ماتریس Distance[i][j] با فرمول زیر به‌روزرسانی و مقدار جدید جایگزین می‌شود.
Distance[i][j] = minimum (Distance[i][j], Distance[i] [B] + Distance[B][j])
۴- رأس C را به عنوان رأس میانی در نظر می‌گیریم. سپس برای هر جفت رأس i و j، مقدار Distance[i][j] را به‌روزرسانی می‌کنیم.
- با بررسی اینکه آیا مسیر از i به j از طریق C کوتاه‌تر از مسیر قبلی است یا خیر، در صورتی که مسیر جدید کوتاه‌تر باشد، مقدار ماتریس Distance[i][j] با فرمول زیر به‌روزرسانی و مقدار جدید جایگزین می‌شود.
Distance[i][j] = minimum (Distance[i][j], Distance[i] [C] + Distance[C][j])
۵- رأس D را به عنوان رأس میانی در نظر می‌گیریم. سپس برای هر جفت رأس i و j، مقدار Distance[i][j] را به‌روزرسانی می‌کنیم.
- با بررسی اینکه آیا مسیر از i به j از طریق D کوتاه‌تر از مسیر قبلی است یا خیر، در صورتی که مسیر جدید کوتاه‌تر باشد، مقدار ماتریس Distance[i][j] با فرمول زیر به‌روزرسانی و مقدار جدید جایگزین می‌شود.
Distance[i][j] = minimum (Distance[i][j], Distance[i] [D] + Distance[D][j])
۶- رأس E را به عنوان رأس میانی در نظر می‌گیریم. سپس برای هر جفت رأس i و j، مقدار Distance[i][j] را به‌روزرسانی می‌کنیم.
- با بررسی اینکه آیا مسیر از i به j از طریق E کوتاه‌تر از مسیر قبلی است یا خیر، در صورتی که مسیر جدید کوتاه‌تر باشد، مقدار ماتریس Distance[i][j] با فرمول زیر به‌روزرسانی و مقدار جدید جایگزین می‌شود.
Distance[i][j] = minimum (Distance[i][j], Distance[i] [E] + Distance[E][j])
۷- در این مرحله از الگوریتم، پس از اینکه تمام گره‌ها به‌عنوان گره‌های میانی در نظر گرفته شده‌اند و ماتریس [][]Distance به‌روزرسانی شده است، حالا می‌توانیم این ماتریس به‌روز شده را به‌عنوان نتیجه نهایی الگوریتم در نظر بگیریم. این ماتریس [][]Distance نشان‌دهنده‌ی کوتاه‌ترین مسیرهای ممکن بین تمامی جفت گره‌ها در گراف است. به عبارت دیگر، با استفاده از این ماتریس می‌توان به راحتی فاصله یا کوتاه‌ترین مسیر بین هر دو گره را پیدا کرد.
پیاده سازی الگوریتم فلوید وارشال
در پیاده‌سازی الگوریتم فلوید وارشال در زبان‌های برنامه‌نویسی مختلف، معمولاً ماتریس جداگانه‌ای به نام [][]dist ایجاد نمی‌شود. به‌جای آن، ماتریس گراف ورودی به‌گونه‌ای تغییر داده می‌شود که نتیجه نهایی در آن ذخیره شود تا پیاده‌سازی ساده‌تر و بهینه‌تر باشد.
در این روش، ماتریس [][]graph به‌طور مستقیم تغییر کرده و به‌عنوان ماتریس نتیجه استفاده می‌شود. کاربران می‌توانند به راحتی پیاده‌سازی را تغییر دهند و [][]dist را به‌عنوان یک کپی از [][]graph مقداردهی اولیه کنند تا تغییرات روی گراف ورودی تأثیری نگذارد. همچنین، برای ساده‌تر کردن پیاده‌سازی، به‌جای استفاده از مقدار بی‌نهایت (Infinity) برای نشان دادن نبود یال بین دو رأس، از مقدار -۱ استفاده کرده‌ایم. این کار به‌ویژه برای کاهش پیچیدگی کد و مدیریت آسان‌تر داده‌ها مفید است.
شبه کد الگوریتم فلوید وارشال
شبکه کد یا Pseudocode به صورت زیر می‌باشد:
for k = 1 to n do:
for i = 1 to n do:
for j = 1 to n do:
if A[i][j] > A[i][k] + A[k][j] then:
A[i][j] = A[i][k] + A[k][j]
– توضیح گام‌به‌گام:
- حلقه اول (حلقه گره میانی): در این حلقه، k به‌عنوان گره میانی انتخاب می‌شود و از ۱ تا n تغییر می‌کند. این گره میانی برای بررسی این که آیا مسیر از گره i به j از طریق k کوتاه‌تر است، استفاده می‌شود.
- حلقه دوم (حلقه گره‌های مبدا): در این حلقه، هر گره i به‌عنوان مبدا انتخاب می‌شود. سپس الگوریتم بررسی می‌کند که برای هر گره مقصد j، آیا مسیر از i به j از طریق گره k کوتاه‌تر از مسیر مستقیم است.
- حلقه سوم (حلقه گره‌های مقصد): در این حلقه، برای هر جفت گره i و j، الگوریتم بررسی می‌کند که آیا مسافت مستقیم از i به j بیشتر از مسافت از i به j از طریق k است یا نه. اگر چنین باشد، مقدار ماتریس فاصله به‌روزرسانی می‌شود.
پس از اتمام تمامی حلقه‌ها، ماتریس فاصله به‌طور کامل به‌روزرسانی شده و کوتاه‌ترین مسیرها بین تمامی جفت‌گره‌ها بدست می‌آید.
الگوریتم فلوید وارشال در پایتون
در زیر سورس کد الگوریتم در زبان برنامه نویسی پایتون آورده شده است:
# Python Program for Floyd Warshall Algorithm
# Solves the all-pairs shortest path
# problem using Floyd Warshall algorithm
def floydWarshall(graph):
V = len(graph)
# Add all vertices one by one to
# the set of intermediate vertices.
for k in range(V):
# Pick all vertices as source one by one
for i in range(V):
# Pick all vertices as destination
# for the above picked source
for j in range(V):
# If vertex k is on the shortest path from
# i to j, then update the value of graph[i][j]
if ((graph[i][j] == -1 or
graph[i][j] > (graph[i][k] + graph[k][j]))
and (graph[k][j] != -1 and graph[i][k] != -1)):
graph[i][j] = graph[i][k] + graph[k][j]
if __name__ == "__main__":
graph = [
[۰, ۴, -۱, ۵, -۱],
[-۱, ۰, ۱, -۱, ۶],
[۲, -۱, ۰, ۳, -۱],
[-۱, -۱, ۱, ۰, ۲],
[۱, -۱, -۱, ۴, ۰]
]
floydWarshall(graph)
for i in range(len(graph)):
for j in range(len(graph)):
print(graph[i][j], end=" ")
print()
الگوریتم فلوید وارشال در سی پلاس پلاس
در زیر سورس کد الگوریتم در زبان برنامه نویسی سی پلاس پلاس آورده شده است:
// C++ Program for Floyd Warshall Algorithm
#include <bits/stdc++.h>
using namespace std;
// Solves the all-pairs shortest path
// problem using Floyd Warshall algorithm
void floydWarshall(vector<vector<int>> &graph) {
int V = graph.size();
// Add all vertices one by one to
// the set of intermediate vertices.
for (int k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (int i = 0; i < V; i++) {
// Pick all vertices as destination
// for the above picked source
for (int j = 0; j < V; j++) {
// If vertex k is on the shortest path from
// i to j, then update the value of graph[i][j]
if ((graph[i][j] == -1 ||
graph[i][j] > (graph[i][k] + graph[k][j]))
&& (graph[k][j] != -1 && graph[i][k] != -1))
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
int main() {
vector<vector<int>> graph = {
{۰, ۴, -۱, ۵, -۱},
{-۱, ۰, ۱, -۱, ۶},
{۲, -۱, ۰, ۳, -۱},
{-۱, -۱, ۱, ۰, ۲},
{۱, -۱, -۱, ۴, ۰}
};
floydWarshall(graph);
for(int i = 0; i<graph.size(); i++) {
for(int j = 0; j<graph.size(); j++) {
cout<<graph[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
الگوریتم فلوید وارشال در جاوا
در زیر سورس کد الگوریتم در زبان برنامه نویسی جاوا آورده شده است:
// Java Program for Floyd Warshall Algorithm
import java.util.*;
class GfG {
// Solves the all-pairs shortest path
// problem using Floyd Warshall algorithm
static void floydWarshall(int[][] graph) {
int V = graph.length;
// Add all vertices one by one to
// the set of intermediate vertices.
for (int k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (int i = 0; i < V; i++) {
// Pick all vertices as destination
// for the above picked source
for (int j = 0; j < V; j++) {
// If vertex k is on the shortest path from
// i to j, then update the value of graph[i][j]
if ((graph[i][j] == -1 ||
graph[i][j] > (graph[i][k] + graph[k][j]))
&& (graph[k][j] != -1 && graph[i][k] != -1))
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
public static void main(String[] args) {
int[][] graph = {
{۰, ۴, -۱, ۵, -۱},
{-۱, ۰, ۱, -۱, ۶},
{۲, -۱, ۰, ۳, -۱},
{-۱, -۱, ۱, ۰, ۲},
{۱, -۱, -۱, ۴, ۰}
};
floydWarshall(graph);
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph.length; j++) {
System.out.print(graph[i][j] + " ");
}
System.out.println();
}
}
}
خروجی پیاده سازی الگوریتم
در این الگوریتم، به کمک سه حلقه تو در تو، همه جفت رئوس گراف بررسی می‌شوند. به ازای هر جفت راس i و j، اگر مسیر جدید از طریق راس k کوتاه‌تر باشد، فاصله به روزرسانی می‌شود. پیچیدگی زمانی الگوریتم فلوید وارشال (n۳)O است، که آن را برای گراف‌های بسیار بزرگ غیر بهینه می‌سازد.
با توجه به مثالی که در بالا برای الگوریتم فلوید وارشال زدیم و توضیحات مربوطه را آوردیم، خروجی سورس کدها به صورت زیر خواهد بود:
۰ ۴ ۵ ۵ ۷ ۳ ۰ ۱ ۴ ۶ ۲ ۶ ۰ ۳ ۵ ۳ ۷ ۱ ۰ ۲ ۱ ۵ ۵ ۴ ۰
کاربردهای عملی الگوریتم فلوید وارشال
الگوریتم فلوید وارشال با وجود سادگی در پیاده‌سازی، به دلیل توانایی‌اش در یافتن کوتاه‌ترین مسیر بین تمامی جفت‌گره‌ها، در بسیاری از حوزه‌های واقعی و صنعتی کاربرد دارد. این الگوریتم در زمینه‌هایی که نیاز به تحلیل سریع و دقیق مسیرها دارند، بسیار مؤثر است. از مسیریابی در شبکه‌های ارتباطی گرفته تا برنامه‌ریزی حمل‌ونقل، رباتیک و سیستم‌های اطلاعات جغرافیایی (GIS)، همگی می‌توانند از این الگوریتم برای تصمیم‌گیری‌های بهینه و صرفه‌جویی در زمان و هزینه بهره ببرند.
مسیریابی در شبکه‌های کامپیوتری
الگوریتم فلوید وارشال می‌تواند برای یافتن کوتاه‌ترین مسیر بین تمامی جفت‌گره‌ها (مثل روترها) در یک شبکه مورد استفاده قرار گیرد. این قابلیت به بهینه‌سازی انتقال داده و جلوگیری از ازدحام در شبکه کمک می‌کند.
برنامه‌ریزی حمل‌ونقل شهری و بین‌شهری
در سیستم‌های حمل‌ونقل، این الگوریتم برای تحلیل و تعیین سریع‌ترین یا کم‌هزینه‌ترین مسیر بین ایستگاه‌ها یا شهرها کاربرد دارد و در طراحی مسیرهای بهینه اتوبوس، قطار و سایر وسایل نقلیه نقش مهمی دارد.
سیستم‌های اطلاعات جغرافیایی (GIS)
در سامانه‌های GIS، این الگوریتم برای تحلیل و محاسبه بهترین مسیر بین موقعیت‌های جغرافیایی مختلف روی نقشه‌ها به‌کار می‌رود؛ مثلاً برای مسیریابی، تحلیل ترافیک یا یافتن نزدیک‌ترین مراکز خدماتی.
مسیریابی ربات‌ها
در رباتیک، از الگوریتم فلوید وارشال برای برنامه‌ریزی حرکت ربات‌ها استفاده می‌شود تا بتوانند سریع‌ترین یا ایمن‌ترین مسیر را میان موانع محیطی پیدا کنند و به مقصد برسند.
نتیجه گیری
الگوریتم فلوید وارشال یکی از الگوریتم‌های قدرتمند و کارآمد برای حل مسئله کوتاه‌ترین مسیر بین تمامی جفت‌گره‌ها در گراف‌های وزن‌دار است. این الگوریتم با استفاده از تکنیک برنامه‌ریزی پویا و به‌روزرسانی تدریجی ماتریس فاصله، قادر است تمامی مسیرهای کوتاه بین گره‌ها را در زمانی با پیچیدگی زمانی (n۳)O محاسبه کند. گرچه برای گراف‌های کوچک و متوسط مناسب است، در گراف‌های بزرگ با تعداد گره‌های زیاد می‌تواند زمان‌بر باشد. با این حال، کاربردهای متنوعی از جمله مسیریابی شبکه‌ها، تحلیل سیستم‌های حمل‌ونقل و رباتیک دارد که آن را به ابزاری ضروری در بسیاری از حوزه‌های علمی و مهندسی تبدیل کرده است.
