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

Question

الگوریتم Dijkstra

 

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

 

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

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

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

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

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

میده 

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

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

 

 

 

Comments

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

Answer 1

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

Comments

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