کوتاه ترین مسیر با دایسترای دوطرفه
دوشنبه, ۱۹ فروردين ۱۳۹۲، ۰۹:۴۱ ق.ظ
برای پیدا کردن کوتاه ترین مسیر بین دو راس مشخص در یک گراف می توان با دایسترای دوطرفه کار کرد که در عمل بسیار عالی است.
دایسترای دو طرفه در واقع با ساختن دو تا گراف از مبدا و مقصد (رو به جلو و رو به عقب) به دست می آید.
با به هم رسیدن این گراف ها الگوریتم پایان می یابد اما این لزوما به این معنی نیست که کوتاه ترین مسیر همان گرافی است که از برخورد این دو گراف به دست می آید. برای همین در دایسترا باید تغییراتی اعمال شود.
این تغییر عبارت است از چک کردن یال های بین مسیر اول و مسیر دوم.
فایل پاور پوینت زیر که توسط خودم درست شده این مطلب را نشان می دهد.
