پیدا کردن طولانی ترین مسیر در DAG - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

پیدا کردن طولانی ترین مسیر در DAG

+1 امتیاز
96 بازدید
اگر یک گراف DAG داشته باشیم آیا امکان پیدا کردن طولانی ترین مسیر وجود داره ؟ یا جزو مشکلات NP_hard هست ؟
سوال شده دی 21, 1393  بوسیله ی PSPCoder (امتیاز 1,411)   2 12 47

1 پاسخ

+2 امتیاز
 
بهترین پاسخ
سلام

ابتدا Topological sort رو اجرا کنید ، سپس موقع Relax کردن بجای انتخاب کمترین وزن ، بیشترین وزن رو به ازای V-1 رئوس از راس ورودی  انتخاب کنید با همان هزینه V+E

مساله مشابه که NP-Hard : یافتن طولانی ترین مسیر بین دو راس در یک گراف بدون وزن ، بدون جهت هست.
پاسخ داده شده دی 21, 1393 بوسیله ی Pakniat (امتیاز 382)   1 4 24
نمیشه بجای انتخاب بیشترین وزن , همه وزن ها رو منفی کرد بعد از الگوریتم پیدا کردن کوتاه ترین مسیر در dag استفاده کرد ؟
تو این نوع گراف چون دور با وزن منفی و کلا دور نداریم مشکلی پیش نمیاد
...