الگوریتم Dijkstra
یک الگوریتم مشابه Dfs :
1- کل حافظه مورد نیاز n هست(به ازای هر راس اندازه 1) ،
2- از راس شروع ، به هر راسی که حرکت می کنیم (Walk ) مجموع مقدار وزن یال تا گره فعلی در یک حافظه نگه داری میشه و در حین اجرا این مقدار افزایش(موقع discovery time ) و یا کاهش(موقع نسبت دادن finishing time و برگشتن) می یابد و به اون راس نسبت داده میشه
3- موقع نسبت دادن discovery time ها ی هر گره مقدار گره ی مورد نظر relax میشه و کمترین مقدار از گره شروع به حافظه در زمان 1 نسبت داده میشه(hash table ) مقدار relaxشده مجموع هزینه هایی است که از راس شروع به آن راس رسیدیم(مرحله 2)
4- در نهایت در حافظه شماره (1) کوتاه ترین مسیر درج شده
در مورد این الگوریتم که گفتم مثال نقضی فعلا براش گیر نیوردم شاید اگر گراف همبند نباشه جواب نده حتی اگر دور منفی هم داشته باشیم در حلقه گیر نمی کنه و جواب درست
میده
(احتمالا یه جا باید غلط باشه وگرنه حتما Dijksra همین الگوریتم رو پیشنهاد میداد :)
مشکل الگوریتم ؟