19. Прима-Дeйкстра алгoритми. Вақт бўйича самарадoрлигини баҳoлаш

Dijkstraning eng qisqa yo'l algoritmi | Ochko'z Algo-7

Grafikadagi manba va vertexni berilgan holda, berilgan grafikdagi manbadan vertikalgacha bo'lgan eng qisqa yo'llarni toping.

Dijkstraning algoritmi Primning minimal daraxtni qisqartirish algoritmiga juda o'xshaydi . Prim's MST singari, biz ildiz sifatida berilgan manbaga ega bo'lgan SPT (eng qisqa yo'l daraxti) yaratamiz. Biz ikkita to'plamni saqlaymiz, bitta to'plamda eng qisqa yo'l daraxtiga kiritilgan uchlari bor, boshqa to'plamda hali eng qisqa yo'l daraxtiga kiritilmagan uchlari mavjud. Algoritmning har bir bosqichida biz boshqa to'plamda joylashgan (hali kiritilmagan to'plam) va manbadan minimal masofaga ega bo'lgan verteksni topamiz.

Quyida Dijkstra algoritmida bitta manbali vertexdan berilgan grafikning barcha boshqa uchlariga eng qisqa yo'lni topish uchun foydalanilgan batafsil qadamlar keltirilgan.
Algoritm
1) Qisqa yo'l daraxti tarkibiga kiritilgan, ya'ni manbadan minimal masofa hisoblab chiqilgan va oxiriga etkaziladigan sptSet (qisqa daraxtlar to'plami) to'plamini yarating . Dastlab, ushbu to'plam bo'sh.
2) Kirish grafigidagi barcha uchlarga masofa qiymatini bering. Barcha masofa qiymatlarini INFINITE sifatida boshlang. Manba cho'qqisi uchun masofa qiymatini 0 sifatida belgilang, shunda u avval tanlanadi.