مقایسه الگوریتم های پیدا کردن کوتاهترین مسیر بین 2 راس در گراف - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

مقایسه الگوریتم های پیدا کردن کوتاهترین مسیر بین 2 راس در گراف

+1 امتیاز
108 بازدید

از بین الگوریتم های زیر

BFS

استفاده از topological sort

BellmanFord

Dijkstra

که برای پیدا کردن کوتاه ترین مسیر بین 2 راس در گراف هستند از هر کدوم چه وقت هایی باید استفاده کرد ؟ و از نظرسرعت اجرا چه تفاوت هایی با هم دارند؟؟

سوال شده دی 1, 1393  بوسیله ی َAI (امتیاز 304)   1 3 26

1 پاسخ

+2 امتیاز

سلام

سوالتون خیلی کلی هست ! یه درجه بدتر سوال این بود که الگوریتم های گراف را نام برده و هر کدام را توضیح دهید در پرانتز با مثال :)

الگوریتم Bfs اگر راس V در فاصله k+1 از راس جاری باشد حتما تمام رئوس در فاصله k رو ملاقات می کنه برای پیاده سازی هم معمولا از یک queue استفاده میشه با زمان خطی

الگوریتم topological sort زمانی استفاده میشه که یک گراف بدون دور و جهت دار داشته باشیم که  معمولا DFs استفاده میشه با زمان خطی

BellmanFord هم موقعی که احتمال وجود وزن منفی در گراف جهت دار موجود باشه اگر داشته باشیم false برمی گردونه و گرنه کوتاه ترین مسیر رو بر می گردونه بازمان EV

Dijksra هم معمولا با یکی از انواع هیپ پیاده سازی میشه و زمان E+VlogV رو داره و به صورت حریصانه عمل می کنه

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

 

پاسخ داده شده دی 16, 1393 بوسیله ی Pakniat (امتیاز 382)   1 4 24
...