الگوریتم پیدا کردن کوتاهترین راه از بین مسیرها

[am_abbas65]

سلام دوستان عزیز

من میخوام یه برنامه بنویسم که از میان مسیرهی موجود کوتاهترین مسیر را برای رسیدن به مقصد پیدا بکنه در واقع نحوه پیاده سازی و الگوریتم جستجوی اونو باید پیدا کنم .

من در اینجا از گراف وزن دار استفاده کرد که وزن یالها نشان دهنده طول مسیر و هزینه مسیر میباشد در شکل که میبینید من میخوام که از نقطه A برم به نقطه B در واقع خیلی مسیر میتونه موجود باشه چون اگه یک شهر رو حساب کنید بینهایت تا راه وجود داره که بری به این نقطه ولی هزینشون خیلی زیاد میشه من در اینجا سه تا مسیر خودم انتخاب کردم که هزینشون متفاوت هست در ضمن رنگهای گراف نشاندهنده مسیر هایی هست که باید طی شوند تا به مقصد برسیم و گرافهایی که دورنگ دارند نشان دهنده این است که از این مسیر چند راه وجود دارد .رنگ زرد مسیر طولانی هست و ابی کوتاهترین مسیر و قهوهای نسبت به ابی کمی هزینش زیاده . خوب اولا نحوه ذخیره سازی مهم هست که من در دیتابیس این مسیر ها و ارتباط اونارو ذخیره کنم و برای یافتن نتیجه از Query استفاده کنم یا اینکه در فایل ذخیره کنم ؟‌ دوم اینکه من بهتره از چه روشی برای جستجو استفاده کنم درخت دودویی یا درخت معمولی یا پشته و یا لیست پیوندی ؟ و الگوریتم اون به چه صورتی هست ؟

لطفا نظرات و راه حل های خودتون رو بفرمایید

[Mahdi.Kiani]

سلام دوستان عزیز

من میخوام یه برنامه بنویسم که از میان مسیرهی موجود کوتاهترین مسیر را برای رسیدن به مقصد پیدا بکنه در واقع نحوه پیاده سازی و الگوریتم جستجوی اونو باید پیدا کنم .

من در اینجا از گراف وزن دار استفاده کرد که وزن یالها نشان دهنده طول مسیر و هزینه مسیر میباشد در شکل که میبینید من میخوام که از نقطه A برم به نقطه B در واقع خیلی مسیر میتونه موجود باشه چون اگه یک شهر رو حساب کنید بینهایت تا راه وجود داره که بری به این نقطه ولی هزینشون خیلی زیاد میشه من در اینجا سه تا مسیر خودم انتخاب کردم که هزینشون متفاوت هست در ضمن رنگهای گراف نشاندهنده مسیر هایی هست که باید طی شوند تا به مقصد برسیم و گرافهایی که دورنگ دارند نشان دهنده این است که از این مسیر چند راه وجود دارد .رنگ زرد مسیر طولانی هست و ابی کوتاهترین مسیر و قهوهای نسبت به ابی کمی هزینش زیاده . خوب اولا نحوه ذخیره سازی مهم هست که من در دیتابیس این مسیر ها و ارتباط اونارو ذخیره کنم و برای یافتن نتیجه از Query استفاده کنم یا اینکه در فایل ذخیره کنم ؟‌ دوم اینکه من بهتره از چه روشی برای جستجو استفاده کنم درخت دودویی یا درخت معمولی یا پشته و یا لیست پیوندی ؟ و الگوریتم اون به چه صورتی هست ؟

لطفا نظرات و راه حل های خودتون رو بفرمایید

اگر درست فهمیده باشم منظورتون را باید به الگوریتم دایجکسترا نگاه کنید
این الگوریتم جهت پیدا کردن کوتاهترین مسیر از گره فرضی a تا گره فرضی b را بهتون میده
این الگوریتم در بدترین حالت مرتبه زمانی n^2 داره که n تعداد گره های گراف است
این الگوریتم برای هر دو گراف جها دار وساده (غیر جهت دار کار می کنه)... تنها برای گراف هایی با که دارای یال هایی با وزن منفی هستند درست کار نمیکنه...پس طبیعتا برای گراف هایی با دور منفی نیز همینطوره
در ضمن حتی با نوشتن یک الگوریتم ناکارامد، (مقایسه تمام راه ها)مرتبه زمانی از نوع فاکتوریل خواهد بود نه بینهایت..

اینجا را هم ببین

و اگر خواستی کوتاهترین مسیر بین هر دو گره از گراف را به دست بیاری از الگوریتم فلوید می تونی استفاده کنی

این هم برای فلوید- وارشال