(۱۷ خرداد ۱۳۹۵ ۱۱:۳۸ ب.ظ)behnam5670 نوشته شده توسط:  

(17 خرداد ۱۳۹۵ ۱۱:۱۴ ب.ظ)kamal3401 نوشته شده توسط:  سلام من از ی سوالی عکس گرفتم میخوام ببینم این به چه شکلی حل میشه

ی روشی بود به اسم دایجکسترا ولی تا اونجایی که میدونم اون روش برای گراف های بدون جهت بود
این گراف جهت داره

میشه راهنمایی کنید

در فایل ضمیمه شده الگوریتم دیکاسترا به همراه مثال گراف جهت‌دار به صورت مرحله به مرحله نشان داده شده است

ممنون
تنها راهش همینه؟
نمیشه مثلا از روش های پریم یا کروسکال تبدیل به درختش کنی و بعد پیدا کنی؟

(۱۷ خرداد ۱۳۹۵ ۱۱:۴۳ ب.ظ)kamal3401 نوشته شده توسط:  

(17 خرداد ۱۳۹۵ ۱۱:۳۸ ب.ظ)behnam5670 نوشته شده توسط:  

(17 خرداد ۱۳۹۵ ۱۱:۱۴ ب.ظ)kamal3401 نوشته شده توسط:  سلام من از ی سوالی عکس گرفتم میخوام ببینم این به چه شکلی حل میشه

ی روشی بود به اسم دایجکسترا ولی تا اونجایی که میدونم اون روش برای گراف های بدون جهت بود
این گراف جهت داره

میشه راهنمایی کنید

در فایل ضمیمه شده الگوریتم دیکاسترا به همراه مثال گراف جهت‌دار به صورت مرحله به مرحله نشان داده شده است

ممنون
تنها راهش همینه؟
نمیشه مثلا از روش های پریم یا کروسکال تبدیل به درختش کنی و بعد پیدا کنی؟

آها ببینید چون شما گفتید که الگوریتم دیکاسترای جهت‌دار، واسه همین من اون فایل فارسی رو دادم. الگوریتم دیکاسترا از یک مبدا شروع میکنه و مینیمم مسیر رو به ازای رأس‌های مختلف بدست میاره. در حالی که چیزی که شما میخواید به نظرم مسأله‌ی فروشنده‌ی دوره گرد هست! از یک رأس شروع کنیم و تمامی رأس‌ها رو با مینیمم مسافت طی کنیم (به همه‌ی شهرها بریم) و برگردیم به نقطه‌ی اول.
واسه این مسأله راه‌حل‌های زیادی ارائه شده منتهی NP-hard هست یعنی جواب در مرتبه‌ی چند جمله‌ای نداره.

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

روش‌های مختلف رو به صورت ویژوآل اینجا میتونی ببینی

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


اما اگه منظور مسأله این هست که از هر گره نسبت به بقیه‌ی گره‌ها مینیمم مسیر رو پیدا کنه، اون موقع باید دیکاسترا بزنید

اگه منظور این هست که از یک گره شروع کنید و تمامی رأس‌ها رو بپیمایید (بدون بازگشت به محل اول) اون موقع میشه چیزی که شما گفتید و از اون دو الگوریتم باید استفاده کنید و فرقی نداره از چه گرهی شروع کنید. به نظرم منظور سؤال همین هست (و نیازی به بازگشت به نقطه‌ی اول نیست)