صفحه‌ها: ۱ ۲
(۱۲ بهمن ۱۳۹۲ ۰۹:۵۱ ب.ظ)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 گفتید رفته، جالبه واسم!
راه حلتون که درسته، من واسم این جالبه که تو دو سال مختلف، یه سؤال دو تا جواب مختلف داشته، نمیدونم چی درسته الان، ممنون .
پاسخ این سوال رو می تونید در لینک زیر ببینید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خلاصه راه حلش اینه:
۱- ترتیب توپولوژیک راس ها رو به کمک 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 به ازای هر گره میشه حساب کرد؛
پ.ن.: البته سوال اصلی که در اون فایل حل شده طولانی ترین مسیر در کل گرافه؛
(۱۳ بهمن ۱۳۹۲ ۰۱:۵۵ ق.ظ)Ghiasoddin نوشته شده توسط: پاسخ این سوال رو می تونید در لینک زیر ببینید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
فایل pdf دانلود نمیشه، لینکش خرابه گویا
(۱۱ بهمن ۱۳۹۲ ۰۸:۴۷ ب.ظ)Riemann نوشته شده توسط: اگه گراف DAG باشه و وزن داشته باشه شما کافی هست وزن ها رو در یه منفی ضرب کنید و بایک بار فراخوانی DFS و به اصلاح Relax کردن میتونید کوتاه ترین مسیر رو در کراف منفی که میشه طولانی ترین در مثبت رو پیدا کنید.البته فکر کنم.
چجوری میشه با DFS طول کوتاهترین مسیر رو بدست آورد ؟
(۱۲ بهمن ۱۳۹۲ ۱۱:۱۴ ق.ظ)nazanin_sh نوشته شده توسط: ممنون دوستان.
منم فکر میکنم با DFS میشه ولی یه مشکلی هست. آیا تضمینی وجود داره که این مسیری که انتخاب میکنیم حتما طولانی ترین مسیر باشه؟
البته وقتی گفته میشه گراف بدون دور، یعنی میتونیم یه درخت جهت دار در نظر بگیریم دیگه نه؟ بنابراین میشه گفت برای رسیدن به هر گره فقط یک مسیر وجود داره پس همون مسیر طولانی ترین مسیر هست؟
نه نمیشه گفت ، مثلا میشه همچین حالتی داشته باشیم
![[تصویر: 247745_gra.JPG]](https://img.manesht.ir/247745_gra.JPG)