حل تشریحی سوال شماره 5 حل مسئله

چند تا از گزاره های زیر صحیح است؟

• اگر پس از اتمام الگوریتم بلمن فورد، به‌روز رسانی فاصله‌ها را ادامه دهیم و فاصله مربوط به یک رأس $\nu$ باز هم به روز شود $\nu$ در یک دور منفی قرار دارد.
• اگر در جست وجوی عمق اول گراف جهت دار G تنها یک یال بازگشتی (e (back edge وجود داشته باشد آنگاه یال $e^{\prime }$ به جز یال e وجود دارد که $G-e^{\prime }$ بدون دور است.
• اگر در الگوریتم دایكسترا که روی یک DAG و از مبدأ اجرا شده، فقط برخی از یالهای خروجی و وزن منفی داشته باشند الگوریتم ممکن است به درستی فاصله ها را محاسبه نکند.