الگوریتم دایکسترا


یک گراف وزن دار جهت دار یا غیر جهت دار با n رأس و m یال داده می شود. وزن تمام لبه ها غیر منفی است. چند راس شروع مشخص شده است. شما باید طول کوتاه ترین مسیرها را از راس s تا همه راس های دیگر پیدا کنید و همچنین راهی برای چاپ کوتاه ترین مسیرها به خودی خود ارائه دهید.
 
این مشکل "مشکل کوتاهترین مسیر تک منبع" نامیده می شود (مشکل کوتاهترین مسیرهای تک منبعی).

وظایف مشابه 1-K BFS را انجام می دهد، اما بدون توجه به K. همچنین، مانند 1-K BFS، لبه های منفی را به درستی کنترل نمی کند

الگوریتم:
الگوریتم دایکسترا خود از N تکرار تشکیل شده است. در تکرار بعدی، راس V  با کمترین فاصله تا آن از میان رئوس هایی که هنوز علامت گذاری نشده اند، این راس مشخص شده و شل شدن رئوس همسایه از آن رخ می دهد.


 رفتار مجانبی نهایی الگوریتم این است: O(n2+ m)

Training problem

Dijkstra: The Beginning (C++)

Training problem

دایکسترا

از آنجایی که رفتار مجانبی اجرای ساده الگوریتم دایکسترا این است: \(O(n^2 + m)\)، پس با افزایش تعداد رئوس، سرعت کار راضی کننده نمی شود.
 ساختارهای داده مختلفی را می توان برای بهبود استفاده کرد: تپه های فیبوناچی، مجموعه های set یا یک صف اولویت priority_queue. 
مثالی را با set در نظر بگیرید، در نتیجه، مجانب نهایی این است: \(O(n log (m))\) ، جزئیات.

Training problem

الگوریتم Dijkstra در مجموعه O(M logN) c: شروع (C++)