|
Deykstra algoritmi qanday ishlaydi?
|
| bet | 2/7 | | Sana | 15.05.2024 | | Hajmi | 46,46 Kb. | | #234563 |
Bog'liq sarviiiiii| Deykstra algoritmi qanday ishlaydi?
Dijkstra algoritmi, bir grafda eng qisqa yo‘lni topish uchun ishlatiladigan bir algoritmdir. Bu algoritm, bir boshlang‘ich tugallanish nuktasidan boshlab qolgan barcha tugallanishlarga olib boriladi va ulardan eng kam miqdorda bo‘lgan tugallanishni topish uchun ishlatiladi.
Algoritmda har bir tugallanish uchun bo‘shlik miqdorini hisoblash uchun vaqt xarajatlari ishlatiladi. Har bir tugallanish uchun bo‘shlik miqdorini aniqlash uchun, boshlang‘ich tugallanish nuktasi orqali qolgan barcha nuktalarga olib boriladi va ulardan eng kam miqdorda bo‘lgan tugallanish tanlanadi. Tanlangan tugallanishning miqdori tugallanish nuktasi orqali barcha nuktalarga yetib borish vaqtida aniqlanadi.
Algoritmda, barcha nuktalarga olib borish uchun grafning to‘g‘ri uzluksiz bo‘lganligini tekshirish uchun DFS yoki BFS kabi qo‘llanmalar ishlatilmaydi. Bu sababli Dijkstra algoritmi orqali eng qisqa yo‘l topish uchun ishlatiladigan vaqt xarajatlari katta bo‘lmaydi.
Algoritmdan kutiladigan natijalar, boshlang‘ich tugallanish nuktasidan barcha nuktalarga eng kam miqdorda borish uchun zarur bo‘lgan bo‘shlik miqdorlarini aniqlaydi. Bu natijalarga asosan, grafda eng qisqa yo‘l yoki minimum ostova ag‘lini topish mumkin.
Grafikadagi manba va vertexni berilgan holda, berilgan grafikdagi manbadan vertikalgacha bo'lgan eng qisqa yo'llarni toping.
3.Deykstriyaning eng qisqa yo’l algoritmi.
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.
|
| |
