تالار گفتمان مانشت

پیدا کردن طولانی ترین مسیر در گراف جهت دار بدون دور از چه مرتبه ای است؟ یعنی از یک راس مبدا شروع کنیم و به راس مقصد برسیم.
میشه در زمان چند جمله ای حلش کرد؟

در حافظه‌ام دارم که استاد سید جوادی فرمودند چون دور نداریم میتونیم روی راس با بیشترین هزینه پیمایش اول عمق بزنیم و در پیمایش اول عمق هم هزینه o(e+n) پیچیدگی ما می باشد
پس درجه پیدا کردن طولانی ترین مسیر چند جمله ای می باشد

منطقی هم می باشد لکن دوستان دیگر تایید کنند...

ممنون ولی مثلا در شکل زیر چطوری با پیمایش اول عمق می شود مسیر را پیدا کرد؟ با شروع از بالاترین راس؟
[attachment=2708]

خوب این قاعده برای گراف بدون جهت بود اما یک نکته وقتی گراف با دور جهت دار داشته باشیم میشه با تغییر در بلمن فورد طولانی ترین مسیر را بدست اورد یعنی o(n^3 حالا که گرافمون بدون دور هست خوب قطعا پیچیدگی از این کمتر میشه


اگر بتونیم جواب این سوال شما را بدیم در حقیقت این سوال را هم جواب دادیم چرا که در این جا هم دنبال بیشترین طول هستیم و مثلث را میشه به گراف جهت دار تبدیل کرد و با توجه به گزینه‌ها قطعا ج.واب چند جمله ای خواهد بود

بله اتفاقا من هم به دنبال این سوال شما رسیدم به این مطلب.

کتاب اقای قلزم گفته اگر در گراف جهت دار بدون دور وزن یال‌ها از مبدا به پایین صعودی باشه کوتاه ترین مسیر و طولانی ترین مسیر با o(n+e)پیدا میشه (اینو بعد از مطالب دکستری به عنوان تمرین داده خوب یعنی مرتبطه دیگه نه؟)
نظر شما چیه

فکر کنم منظورش topological sort هست. ولی اینجا که به صورت صعودی مرتب نیست ؟
شکلش این طوری میشه درسته؟
[attachment=2710]

نه چرا فک کردی منظورش اینه؟
این شکل که شما کشیدی صعودی نیست که
این نکته اقای قلزم به خاطر تو این تاپیگ گفتم که بگم بله طولانی ترین مسیر گراف جهت دار در زمان چند جمله ای قابل حله اما به شرط صعودی بودن یالها

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

این‌ها رو نگاه کنید.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

صفحه ۱۷ pdf
[attachment=2711]
فکر کنم اگه وزن همه‌ی یال‌ها منفی بود مییشد حل کرد . همه‌ی یال‌ها رو در -1 ضرب می کردیم با دیکسترا کوتاهترین مسیر رو پیدا می کردیم. بعد هم در آخر جواب آخر را در -1 ضرب می کردیم.

لینک مشاهده کردم دوست من:
جوای اون مساله را را تو تاپیگش میدم حتما نظرتون را بگید اما به نظرتون میشه کلا با عمقی و سطحی بهترین مسیر را تو گراف های جهت داری پیدا کرد اگر ترتیب یالها صعودی نباشه؟