برای اینکه این مساله جواب چند جمله ای داشته باشه، باید بتونیم با روشهای پویا حلش کنیم

و برای استفاده از الگوریتم های پویا باید در مساله اصل بهینگی صادق باشه
اصل بهینگی یک حل بهینه برای نمونه ای از مساله همواره حاوی حل بهینه برای همه زیرنمونه ها باشد

اگر گراف دور داشته باشه ، اصل بهینگی برای صادق نیست:
مثلا در شکل پیوست؛ طولانی ترین مسیر از v1 به v4 میشه: v1,v3,v2,v4
که در اون زیر مسیر v1 به v3 طولانی ترین نیست. بلکه طولانی ترین مسیر v1,v2,v3 است.

این اتفاق به خاطر وجود دور افتاد.

پس در گرافهای دارای دور نمی تونیم الگوریتمی با مرتبه چند جمله ای داشته باشیم.

ولی در صورت عدم وجود دور اصل بهینگی برای مساله صادق است و میشه با کمی تغییر از الگوریتم فلوید(به جای min بنویسیم max) براشون استفاده کنیم که درجه چندجمله ای داره