(۲۲ آذر ۱۳۹۳ ۰۹:۱۱ ب.ظ)alwaysPeace نوشته شده توسط:  سلام
در شکل زیر هدف پیدا کردن کوتاه ترین مسیر (با استفاده از الگوریتم دیکسترا) از گره A به گره D است که ۶ مرحله اول رو طبق شکل نشون داده.
من متوجه نشدم وقتی از E اومد به G ، (شکل d) ، چطوری بعدش دوباره رفت به گره F (در شکل e)؟ علتش رو میدونم چون اگه از F بره هزینه مسیر تا رسیدن به H کمتر میشه و به جای ۹، ۸ میشه. اما متوجه نشدم الگوریتم به چه روشی اینو انجام داد..

ببین کلا روشش همینه دیگه.
شما اون راسهای سیاه رو همیشه باید درنظر بگیری
یعنی همیشه باید مسیری رو انتخاب کنی که هزینه طی شده + هزینه که قراره طی کنیم ، کمتر باشه
واسه همینم شما باید در هر مرحله اجرای الگوریتم یالهای متصل به راسهای ملاقات شده رو با هم در نظر بگیری و کمترین هزینه طی شده + هزینه که قراره طی بشه رو انتخاب کنی

(۲۲ آذر ۱۳۹۳ ۰۹:۴۲ ب.ظ)explorer نوشته شده توسط:  

(22 آذر ۱۳۹۳ ۰۹:۱۱ ب.ظ)alwaysPeace نوشته شده توسط:  سلام
در شکل زیر هدف پیدا کردن کوتاه ترین مسیر (با استفاده از الگوریتم دیکسترا) از گره A به گره D است که ۶ مرحله اول رو طبق شکل نشون داده.
من متوجه نشدم وقتی از E اومد به G ، (شکل d) ، چطوری بعدش دوباره رفت به گره F (در شکل e)؟ علتش رو میدونم چون اگه از F بره هزینه مسیر تا رسیدن به H کمتر میشه و به جای ۹، ۸ میشه. اما متوجه نشدم الگوریتم به چه روشی اینو انجام داد..

ببین کلا روشش همینه دیگه.
شما اون راسهای سیاه رو همیشه باید درنظر بگیری
یعنی همیشه باید مسیری رو انتخاب کنی که هزینه طی شده + هزینه که قراره طی کنیم ، کمتر باشه
واسه همینم شما باید در هر مرحله اجرای الگوریتم یالهای متصل به راسهای ملاقات شده رو با هم در نظر بگیری و کمترین هزینه طی شده + هزینه که قراره طی بشه رو انتخاب کنی

خب ببینید الان فرض کنید ما تو راس G اومدیم، مرحله بعدی تنها راسی که میتونیم بریم راس H هست. میایم هزینشو حساب می کنیم میبینیم برابره با ۹. خب اینجا دو باره بر میگردیم عقب (تو راس E) و بعد حساب می کنیم که اگه از E بخوایم بریم به H هزینش چه قدر میشه و اگه کمتر بود اونو جایگزین کنیم و باید برای هر گره این کارو انجام بدیم. ولی این کار تو دستور کار الگوریتم دیکسترا گفته نشده و تو مراحلش نیست..!

(۲۲ آذر ۱۳۹۳ ۱۰:۲۸ ب.ظ)alwaysPeace نوشته شده توسط:  خب ببینید الان فرض کنید ما تو راس G اومدیم، مرحله بعدی تنها راسی که میتونیم بریم راس H هست. میایم هزینشو حساب می کنیم میبینیم برابره با ۹. خب اینجا دو باره بر میگردیم عقب (تو راس E) و بعد حساب می کنیم که اگه از E بخوایم بریم به H هزینش چه قدر میشه و اگه کمتر بود اونو جایگزین کنیم و باید برای هر گره این کارو انجام بدیم. ولی این کار تو دستور کار الگوریتم دیکسترا گفته نشده و تو مراحلش نیست..!

شما باید برای ادامه تمام یالهای متصل به راسهای سیاه شده در نظر بگیری نه فقط آخرین یال.
یعنی شما وقتی به G رسیدی تنها یال GH مد نظر نیست بلکه علاوه بر اون باید یالهای EF و CB رو هم در نظر بگیری چون که اینها متصل به راسهای ملاقات شده هستند

(۲۲ آذر ۱۳۹۳ ۱۰:۳۹ ب.ظ)explorer نوشته شده توسط:  

(22 آذر ۱۳۹۳ ۱۰:۲۸ ب.ظ)alwaysPeace نوشته شده توسط:  خب ببینید الان فرض کنید ما تو راس G اومدیم، مرحله بعدی تنها راسی که میتونیم بریم راس H هست. میایم هزینشو حساب می کنیم میبینیم برابره با ۹. خب اینجا دو باره بر میگردیم عقب (تو راس E) و بعد حساب می کنیم که اگه از E بخوایم بریم به H هزینش چه قدر میشه و اگه کمتر بود اونو جایگزین کنیم و باید برای هر گره این کارو انجام بدیم. ولی این کار تو دستور کار الگوریتم دیکسترا گفته نشده و تو مراحلش نیست..!

شما باید برای ادامه تمام یالهای متصل به راسهای سیاه شده در نظر بگیری نه فقط آخرین یال.
یعنی شما وقتی به G رسیدی تنها یال GH مد نظر نیست بلکه علاوه بر اون باید یالهای EF و CB رو هم در نظر بگیری چون که اینها متصل به راسهای ملاقات شده هستند

بله درسته، خیلی ممنوون