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

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


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

الگوریتمی مشابه Dijkstra

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

الگوریتم Dijkstra

 

یک الگوریتم مشابه Dfs :

 

1-  کل حافظه مورد نیاز n هست(به ازای هر راس اندازه 1) ،

2- از راس شروع ، به هر راسی که حرکت می کنیم (Walk ) مجموع مقدار وزن  یال تا گره فعلی در یک حافظه نگه داری میشه و در حین اجرا این مقدار افزایش(موقع discovery time ) و یا کاهش(موقع نسبت دادن finishing time و برگشتن) می یابد و به اون راس نسبت داده میشه

3- موقع نسبت دادن  discovery time ها ی هر گره مقدار گره ی مورد نظر relax میشه و کمترین مقدار از گره شروع به حافظه در زمان 1 نسبت داده میشه(hash table ) مقدار relaxشده مجموع هزینه هایی است که از راس شروع به آن راس رسیدیم(مرحله 2)

4- در نهایت در حافظه شماره (1) کوتاه ترین مسیر درج شده

در مورد این الگوریتم که گفتم مثال نقضی فعلا براش گیر نیوردم شاید اگر گراف همبند نباشه جواب نده حتی اگر دور منفی هم داشته  باشیم در حلقه گیر نمی کنه و جواب درست

میده 

(احتمالا یه جا باید غلط باشه وگرنه حتما Dijksra همین الگوریتم رو پیشنهاد میداد :)

مشکل الگوریتم ؟

 

 

 

سوال شده دی 28, 1393  بوسیله ی Pakniat (امتیاز 382)   1 4 24
قسمت کاهش وزن تا گره فعلی رو چطور میخواهید انجام بدید ؟

1 پاسخ

0 امتیاز

شبیه شکل زیر ، فقط discovery , Finishing time روی روی یال باید قرار بدیم و یه جور Fringe داریم که موقعی که برگشت کردیم مقدار یال ازش کم میشه

shortest path, dijkstra, گراف, پیچیدگی زمانی, پیچیدگی الگوریتم, طراحی الگوریتم

پاسخ داده شده دی 29, 1393 بوسیله ی Pakniat (امتیاز 382)   1 4 24
شما فرض کردید که با یکبار پیمایش و انجام DFS کوتاهترین مسیر پیدا میشه ولی این طور نیست برای نمونه :
http://www.7khatcode.com/?qa=blob&qa_blobid=9192805848419601480
داخل گراف لینک بالا اگر از S اول  برید به P بعد به t بعد به q چون از t یکبار گذشتیم پس به q دیگه نمیتونیم برسیم و کوتاه ترین مسیر بین s-q اشتباه بدست میاد.(اگر هم بخواهید اجازه بدید که بیشتر از یکبار از یک راس عبور بشه داشتن دور مشکل ساز میشه )
کاری که شما انجام دادید تقریبا شبیه پیدا کردن کوتاهترین مسیر در DAG هست (که با استفاده ازtopological sort و DFS انجام میشه )
...