میشه با dfs پیمایش کرد و به هر گره ای که رسیدیم هزینه مسیر رو روی گره بنویسیم و اگر از مسیر دیگه هم رسیدیم مقایسه میکنیم هزینه کدوم بیشتره اگه بیشتر بود جایگزین میکنیم. گزینه ۲ درست

پاسخ این سوال رو می تونید در لینک زیر ببینید:

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


خلاصه راه حلش اینه:
۱- ترتیب توپولوژیک راس ها رو به کمک DFS پیدا کنید و اونها را توی یه ردیف پشت هم قرار بدید و سپس یالها رو از روی گراف اصلی رسم کنید؛ نتیجه اینکار میشه یه گراف خطی (شکل ۳ صفحه ۲)؛

۲- فرض کنید با توجه به شکل به دست اومده، بخایم طولانی ترین مسیر از S به D رو حساب کنیم؛ این طولانی ترین مسیر از یکی از گره ها ماقبل (predecessor) گره D یعنی B یا C میگذره؛ پس میشه اینطور بنویسیم:
[tex]dis(D)=max\{dis ( C ) 1,dis(B) 1\}[/tex]
و به طور کلی برای هر گره:
[tex]dis(v)=max_{(u,v)\in E}\{dis(u) 1\}[/tex]
که رابطه بالا رو با یکبار اجرای مجدد DFS به ازای هر گره میشه حساب کرد؛

پ.ن.: البته سوال اصلی که در اون فایل حل شده طولانی ترین مسیر در کل گرافه؛

اول شرط relax رو به جای کوچکتر بزرگتر کن
بعد مرتب سازی توپولوژیک انجام می دی
بعد از همون راس به ترتیب relax می کنی موقعی به یه نود می رسی با ماکس مقایسه کن

من فکر میکنم گزینه ۲ بشه. چون گراف بدون دوره، میشه با bfs این کار رو کرد فکر کنم.

Sent from my SM-T210R using Tapatalk

(۱۱ بهمن ۱۳۹۲ ۰۳:۳۱ ب.ظ)hoomanab نوشته شده توسط:  من فکر میکنم گزینه ۲ بشه. چون گراف بدون دوره، میشه با bfs این کار رو کرد فکر کنم.

Sent from my SM-T210R using Tapatalk

ممنون . ببخشید میشه بیشتر توضیح بدید.
این طولانی ترین مسیرهارو خواسته که. BFS کوتاهترین مسیرهارو پیدا میکرد اونم زمانی که وزن همه یالها یکسان باشه.

باید روندش عوض شه و بزرگترین رو به دست بیاره

Sent from my SM-T210R using Tapatalk

(۱۱ بهمن ۱۳۹۲ ۰۵:۴۰ ب.ظ)hoomanab نوشته شده توسط:  باید روندش عوض شه و بزرگترین رو به دست بیاره

Sent from my SM-T210R using Tapatalk

ممنون بابت پاسخ کاملتون

اگه گراف DAG باشه و وزن داشته باشه شما کافی هست وزن ها رو در یه منفی ضرب کنید و بایک بار فراخوانی DFS و به اصلاح Relax کردن میتونید کوتاه ترین مسیر رو در کراف منفی که میشه طولانی ترین در مثبت رو پیدا کنید.البته فکر کنم.

ممنون دوستان.
منم فکر میکنم با DFS میشه ولی یه مشکلی هست. آیا تضمینی وجود داره که این مسیری که انتخاب میکنیم حتما طولانی ترین مسیر باشه؟
البته وقتی گفته میشه گراف بدون دور، یعنی میتونیم یه درخت جهت دار در نظر بگیریم دیگه نه؟ بنابراین میشه گفت برای رسیدن به هر گره فقط یک مسیر وجود داره پس همون مسیر طولانی ترین مسیر هست؟

ولی فکر کنم با bfs هم بشه. سرعتشون که یکسانه. به هر نود که رسید، مقدار ماکس رو آپدیت میکنه.

Sent from my SM-T210R using Tapatalk

اساتید این سؤال هم همینه آیا ؟!!!


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


اگه یکیه، چرا تو یه کتاب واسه هر کدوم جوابا مختلف واسش هست؟!

(۱۲ بهمن ۱۳۹۲ ۰۸:۴۵ ب.ظ)minami نوشته شده توسط:  اساتید این سؤال هم همینه آیا ؟!!!


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


اگه یکیه، چرا تو یه کتاب واسه هر کدوم جوابا مختلف واسش هست؟!

اینجا dag داریم قضیه اش فرق داره

(۱۲ بهمن ۱۳۹۲ ۰۹:۲۷ ب.ظ)izadan11 نوشته شده توسط:  

(12 بهمن ۱۳۹۲ ۰۸:۴۵ ب.ظ)minami نوشته شده توسط:  اساتید این سؤال هم همینه آیا ؟!!!


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


اگه یکیه، چرا تو یه کتاب واسه هر کدوم جوابا مختلف واسش هست؟!

اینجا dag داریم قضیه اش فرق داره

مگه DAG گراف بدون دور جهت دار نیست؟ ویژگی دیگه ای هم داره من نمیدونم ؟

(۱۲ بهمن ۱۳۹۲ ۰۹:۴۹ ب.ظ)minami نوشته شده توسط:  مگه DAG گراف بدون دور جهت دار نیست؟ ویژگی دیگه ای هم داره من نمیدونم ؟

سوال اونجا رو بد دیدم
(دنبال کلمه ی دور بودم اشتباه نوشته بود ندیدمش)
حق با شماست

(۱۲ بهمن ۱۳۹۲ ۰۹:۵۱ ب.ظ)izadan11 نوشته شده توسط:  

(12 بهمن ۱۳۹۲ ۰۹:۴۹ ب.ظ)minami نوشته شده توسط:  مگه DAG گراف بدون دور جهت دار نیست؟ ویژگی دیگه ای هم داره من نمیدونم ؟

سوال اونجا رو بد دیدم
(دنبال کلمه ی دور بودم اشتباه نوشته بود ندیدمش)
حق با شماست

آره بد نوشته شده

من کتاب پارسه دارم، واسه حل اون سؤال سال ۸۷، از فلوید و بلمن فورد تغییر یافته رفته، جواب سازمان سنجش هم (O(v^3 هست، ولی این سؤالی که تو این صفحه هست رو از روشی که شما با dfs گفتید رفته، جالبه واسم!

(۱۲ بهمن ۱۳۹۲ ۱۰:۰۱ ب.ظ)minami نوشته شده توسط:  

(12 بهمن ۱۳۹۲ ۰۹:۵۱ ب.ظ)izadan11 نوشته شده توسط:  

(12 بهمن ۱۳۹۲ ۰۹:۴۹ ب.ظ)minami نوشته شده توسط:  مگه DAG گراف بدون دور جهت دار نیست؟ ویژگی دیگه ای هم داره من نمیدونم ؟

سوال اونجا رو بد دیدم
(دنبال کلمه ی دور بودم اشتباه نوشته بود ندیدمش)
حق با شماست

آره بد نوشته شده

من کتاب پارسه دارم، واسه حل اون سؤال سال ۸۷، از فلوید و بلمن فورد تغییر یافته رفته، جواب سازمان سنجش هم (O(v^3 هست، ولی این سؤالی که تو این صفحه هست رو از روشی که شما با dfs گفتید رفته، جالبه واسم!

خیلی تست نزدم و اینجور تستا رو درست نخوندم شاید راه حلم جواب نده فقط اون چیزی که فکر کردم نوشتم(منظورم اینه که رو جوابم زیاد فکر نکردم شاید مشکل داشته باشه)

(۱۲ بهمن ۱۳۹۲ ۱۰:۱۵ ب.ظ)izadan11 نوشته شده توسط:  

(12 بهمن ۱۳۹۲ ۱۰:۰۱ ب.ظ)minami نوشته شده توسط:  

(12 بهمن ۱۳۹۲ ۰۹:۵۱ ب.ظ)izadan11 نوشته شده توسط:  

(12 بهمن ۱۳۹۲ ۰۹:۴۹ ب.ظ)minami نوشته شده توسط:  مگه DAG گراف بدون دور جهت دار نیست؟ ویژگی دیگه ای هم داره من نمیدونم ؟

سوال اونجا رو بد دیدم
(دنبال کلمه ی دور بودم اشتباه نوشته بود ندیدمش)
حق با شماست

آره بد نوشته شده

من کتاب پارسه دارم، واسه حل اون سؤال سال ۸۷، از فلوید و بلمن فورد تغییر یافته رفته، جواب سازمان سنجش هم (O(v^3 هست، ولی این سؤالی که تو این صفحه هست رو از روشی که شما با dfs گفتید رفته، جالبه واسم!

خیلی تست نزدم و اینجور تستا رو درست نخوندم شاید راه حلم جواب نده فقط اون چیزی که فکر کردم نوشتم(منظورم اینه که رو جوابم زیاد فکر نکردم شاید مشکل داشته باشه)

راه حلتون که درسته، من واسم این جالبه که تو دو سال مختلف، یه سؤال دو تا جواب مختلف داشته، نمیدونم چی درسته الان، ممنون .

کلا فکر کنم چون دور نداریم از BFS یا DFS استفاده کنیم فرقی نداره هر دوش یه جواب میده. چون برای رسیدن به هر نود فقط یه راه داریم!
درست میگم دیگه؟

(۱۳ بهمن ۱۳۹۲ ۰۱:۵۵ ق.ظ)Ghiasoddin نوشته شده توسط:  پاسخ این سوال رو می تونید در لینک زیر ببینید:

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

فایل pdf دانلود نمیشه، لینکش خرابه گویا

---

(۱۱ بهمن ۱۳۹۲ ۰۸:۴۷ ب.ظ)Riemann نوشته شده توسط:  اگه گراف DAG باشه و وزن داشته باشه شما کافی هست وزن ها رو در یه منفی ضرب کنید و بایک بار فراخوانی DFS و به اصلاح Relax کردن میتونید کوتاه ترین مسیر رو در کراف منفی که میشه طولانی ترین در مثبت رو پیدا کنید.البته فکر کنم.

چجوری میشه با DFS طول کوتاهترین مسیر رو بدست آورد ؟

---

(۱۲ بهمن ۱۳۹۲ ۱۱:۱۴ ق.ظ)nazanin_sh نوشته شده توسط:  ممنون دوستان.
منم فکر میکنم با DFS میشه ولی یه مشکلی هست. آیا تضمینی وجود داره که این مسیری که انتخاب میکنیم حتما طولانی ترین مسیر باشه؟
البته وقتی گفته میشه گراف بدون دور، یعنی میتونیم یه درخت جهت دار در نظر بگیریم دیگه نه؟ بنابراین میشه گفت برای رسیدن به هر گره فقط یک مسیر وجود داره پس همون مسیر طولانی ترین مسیر هست؟

نه نمیشه گفت ، مثلا میشه همچین حالتی داشته باشیم