با عرض سلالم خدمت تمامی دوستان.بنده دارم خودمو واسه آزمون ارشد آماده میکنم.اما متاسفانه در رابطه با الگوریتم دایجکسترا به مشکل بر خوردم.یه راه حل خوب میخوام واسش پیدا کنم.لطفا راهنماییم کنین.با تشکر
الگوریتم دایجسترا خودش راه حله. برای پیدا کردن کوتاه ترین مسیر از یک گره مشخص به بقیه گرهها در گراف جهت دار (یا غیر جهت دار)
اگر مشکل تون درک الگوریتم، یک جمله می گم بهتون که درکش کنید کامل.
بهترین مسیر از گره شروع به هر یک از گره های گراف:
۱- یا اتصال مستقیمه
۲- یا اتصال غیر مستقیم
اگر مستقیم باشه که طول یال روش نوشته شده (هزینه مسیر)
اگر غیر مستقیم باشه باید از طریق کوتاهترین راهی که به گره های ماقبلش رسیدید، به این برسید.
کلا الگوریتم دایجکسترا همونطور که دوستمون گفتند کار میکنه و تو سوالات کنکور هم خوب نمیتونن که یه گراف بزرگ یا پیچیده بدن.اما نکته مهمی که جای سوال دادن داره نحوه پیاده سازی و مرتبه زمانیش هست.
حالا به صورت کلی میگم اما اگه میخوای به صورت خیلی خوب و مفهومی بفهمی باید به کتاب طراحی الگوریتم هورویتز مراجعه کنی تو همه منابع و مراجع این کتاب از همه زیباتر توضیح داده.
این مسئله از زیر مسائل کوتاه ترین مسیر‌ها از منبع واحد هستش.
به این صورت که
۱-از مورد نظر شروع میکنی.
۲-حالا همه راس‌ها رو لیست میکنی اگه مسیر مستقیم به راس شروع بود مقدار بزار در غیر این صورت بی نهایت
۳-حالا اولین راس مجاور رو انتخاب کن فرقی نمیکنه اگه دوتاراس بود اونی که مثلا ایندکسش کمتره
۴-حالا دوباره فاصله از راس مورد نظر رو به همه رئوس با توجه به واسطه گری این راس جدید بررسی کن اگه کمتر شد تو لیست کوتاه ترین مسیر فاصله جدید رو جایگزین کن در غیر این صورت که هیچی
۵-حالا همین کار رو برای راس جدید تکرار کن تا همه رئوس ملاقات بشه همین