(۰۳ اردیبهشت ۱۳۹۴ ۰۸:۲۹ ب.ظ)ashy نوشته شده توسط:  چندین جا مطرح شده اگر سهم ها رو به صورت منفی لگاریتم در نظر بگیریم و بعد الگوریتم بلمن فورد رو اجرا کنیم جواب میده اما من میخواستم بدونم چطور میشه اون دور رو پیدا کرد ؟ متشکرم

سلام
تو این مسئله ما هیچ کاری با وزنها نداریم (جز ضرب کردن و مقایسه‌ی حاصل با ۱).
همون طور که خودتون هم مطرح کردین مسئله فقط تکرار روی حلقه‌های این گرافه. نکته اینجاست که یک گراف میتونه حلقه‌های خیلی زیادی داشته باشه اما خوشبختانه لازم نیست که همه‌ی حلقه‌ها بررسی بشن.

تنها کافیه روی گراف جستجوی اول عمق انجام بشه و اگه در بین حلقه‌های حاصل از back edgeهای این پیمایش پاسخی پیدا نشه، تضمین می‌شه که حلقه‌ی فرصت نداریم؛ چون این حلقه‌ها بنیادی هستند و همه‌ی حلقه‌های دیگه از روی اینها ساخته میشن.