اگر یک نمودار دارای چرخه هایی با وزن منفی است، به طور رسمی الگوریتم فلوید-وارشال برای چنین نموداری قابل اجرا نیست.
در واقع، برای آن جفت رئوس i و j که بین آنها نمی‌توان چرخه وزن منفی را وارد کرد، الگوریتم به درستی کار می‌کند.
برای همان جفت رئوس که پاسخی برای آنها وجود ندارد (به دلیل وجود یک چرخه منفی در مسیر بین آنها)، الگوریتم فلوید تعدادی عدد (احتمالاً به شدت منفی، اما نه لزوما) را به عنوان پاسخ پیدا می کند. با این حال، الگوریتم فلوید را می توان بهبود بخشید تا این جفت رئوس را به طور منظم مدیریت کند و خروجی به عنوان مثال \(- \infty\) داشته باشد.
برای انجام این کار، به عنوان مثال، معیار "عدم وجود مسیر" را می توان انجام داد. بنابراین، اجازه دهید الگوریتم فلوید معمولی روی این نمودار کار کند. سپس کوتاهترین مسیری بین رئوس i و j اگر و فقط در صورتی وجود داشته باشد که یک راس t قابل دسترسی از i و از آن j قابل دسترسی باشد، که برای آن \(d [t][t]<0\).
علاوه بر این، هنگام استفاده از الگوریتم فلوید برای نمودارهایی با چرخه های منفی، باید به خاطر داشت که فواصلی که در فرآیند کار به وجود می آیند می توانند با هر فاز به صورت نمایی منفی پیش بروند. بنابراین، باید با محدود کردن تمام فواصل از پایین به مقداری (به عنوان مثال، \(- \infty\)) از سرریز اعداد صحیح مراقبت کنید.
به صورت کلامی، راه حل را می توان به شرح زیر توصیف کرد:
پس از اینکه الگوریتم فلوید-وارشال برای نمودار ورودی کار کرد، بیایید روی همه جفت رئوس \((i,j)\) و برای هر جفت از این قبیل تکرار کنیم. بررسی می کنیم، بی نهایت کوتاه ترین مسیر از i به j کوچک است یا خیر. برای انجام این کار، بیایید روی سومین راس t تکرار کنیم، و اگر معلوم شد که \(d[t][t] < 0\) (یعنی در چرخه وزن منفی قرار دارد)، و از i و j — سپس مسیر \((i,j)\) می تواند بی نهایت کوچک باشد.