Dijkstra algoritmi
Ikki shahar orasidagi eng qisqa yo'lni topish — ko'rinishda oddiy masala. Lekin "qisqa" deyilganda masofani nazarda tutamiz: ba'zan ikki qadam qilish uchta qadamdan uzoqroq bo'lishi mumkin. Og'irliksiz grafda BFS ishlaydi — u qirralar soni bo'yicha eng qisqani topadi. Ammo qirralarning og'irligi har xil bo'lsa, BFS noto'g'ri natija berishi mumkin.
BFSga ko'ra A → B → D va A → D ikkitadan bir xil: ikkalasi ham 2 ta qirra. Lekin og'irliklar bilan hisoblasak, A → B → D = 1 + 1 = 2, A → D = 10. BFS noto'g'ri javob beradi.
Dijkstra algoritmi aynan shu muammoni hal qiladi: qirralar og'irligi bor, manfiy bo'lmagan grafda bitta manbadan barcha boshqa vertexlargacha eng kichik og'irlik yig'indili yo'lni topadi.
Asosiy g'oya
Dijkstraning markaziy fikri shunda: hozircha ma'lum bo'lgan eng qisqa masofa bo'yicha eng yaqin vertexdan davom et.
Tasavvur qiling, shahardan shaharni kashf qilib chiqyapsiz. Har doim qo'lingizdagi eng yaqin, hali to'liq ishlov berilmagan shaharni tanlab uning qo'shnilarini tekshirasiz. Agar yangi yo'l orqali qo'shniga yetib borish narxi avvalgi ma'lum yo'ldan arzonroq bo'lsa — yangisini yozasiz. Aks holda avvalgisini saqlaymiz.
Bu greedy (ochko'z) yondashuv: har qadamda lokal jihatdan eng yaxshi tanlov qilinadi. Manfiy bo'lmagan og'irliklar bilan bu global optimal natija beradi. Sababi: "eng yaqin" deb belgilangan vertexga allaqachon optimal yo'l topilgan — keyinchalik undan ham yaxshiroq yo'l paydo bo'lishi mumkin emas.
Priority queue: eng yaqinni tanlash
Har qadamda "hozircha ma'lum eng qisqa masofali vertex" tanlanadi. Buni samarali amalga oshirish uchun min-heap yoki priority queue (ustuvorlikli navbat) kerak.
Priority queue oddiy queuedan farqli: elementlar ustuvorlik — bu holda masofaga qarab — tartibida chiqariladi. Eng kichik masofali element doim birinchi chiqadi.
Oddiy queue (FIFO):
kiritish: 5, 2, 8, 1
chiqarish: 5, 2, 8, 1 // kiritish tartibida
Min-heap priority queue:
kiritish: (5, A), (2, B), (8, C), (1, D)
chiqarish: (1, D), (2, B), (5, A), (8, C) // masofaga ko'ra
Priority queue'ga (masofa, vertex) juftliklari solinadi. Har safar eng kichik masofali juft chiqariladi.
Relaxation operatsiyasi
Dijkstrada relaxation markaziy operatsiya:
dist[u] — u vertexigacha hozircha ma'lum eng qisqa masofa. weight(u, v) — udan vga qirra og'irligi. Agar u orqali vga borish avvalgi ma'lum yo'ldan arzonroq bo'lsa, dist[v] yangilanadi.
"Relaxation" nomi shundan: oldingi qattiq, pessimistik baho yumshatiladi — yaxshilanadi. Algoritm boshida barcha masofalar cheksiz (INFINITY) deb olinadi, keyin asta-sekin haqiqiy qiymatlarga yaqinlashib "relax" qilinadi.
Algoritmning to'liq pseudokodi
FUNCTION DIJKSTRA(graph, start)
dist = barcha vertexlar uchun INFINITY bo'lgan map
dist[start] = 0
priority_queue = bo'sh min-heap
priority_queue.INSERT((0, start)) // (masofa, vertex)
visited = bo'sh set
WHILE priority_queue bo'sh emas
(current_dist, current) = priority_queue.EXTRACT_MIN()
IF current visited ichida bo'lsa
CONTINUE // eskirgan yozuv
visited ga current ni qo'sh
FOR har bir (neighbor, weight) graph.adjacency[current] ichida
new_dist = dist[current] + weight
IF new_dist < dist[neighbor]
dist[neighbor] = new_dist
priority_queue.INSERT((new_dist, neighbor))
RETURN dist
Muhim detallar:
- Eskirgan yozuv: priority queue ichida bir vertex uchun bir nechta
(masofa, vertex)yozuvi bo'lishi mumkin. Vertex allaqachon visited bo'lsa — eski yozuv bilan ishlanyapti, o'tkazib yuboriladi. - Visited belgilash extract_min paytida: vertex birinchi marta chiqarilganda uning masofasi final. Manfiy bo'lmagan og'irliklar bilan bu kafolatlanadi: keyinchalik unga yaxshiroq yo'l topilishi mumkin emas.
Bosqichma-bosqich dry run
Quyidagi grafni ko'rib chiqamiz:
Start: A. Boshlang'ich holat:
Qadam 1 — Extract: (0, A)
A visited qilinadi.
Qo'shnilar:
B: 0 + 2 = 2 < ∞ → dist[B] = 2, PQ ga (2, B)
D: 0 + 6 = 6 < ∞ → dist[D] = 6, PQ ga (6, D)
dist: A=0, B=2, D=6, boshqalar ∞
PQ: [(2, B), (6, D)]
Qadam 2 — Extract: (2, B)
B visited qilinadi.
Qo'shnilar:
A: 2 + 2 = 4 > dist[A]=0 → yangilanmaydi
C: 2 + 3 = 5 < ∞ → dist[C] = 5, PQ ga (5, C)
E: 2 + 8 = 10 < ∞ → dist[E] = 10, PQ ga (10, E)
dist: A=0, B=2, C=5, D=6, E=10, F=∞
PQ: [(5, C), (6, D), (10, E)]
Qadam 3 — Extract: (5, C)
C visited qilinadi.
Qo'shnilar:
B: 5 + 3 = 8 > dist[B]=2 → yangilanmaydi
F: 5 + 1 = 6 < ∞ → dist[F] = 6, PQ ga (6, F)
dist: A=0, B=2, C=5, D=6, E=10, F=6
PQ: [(6, D), (6, F), (10, E)]
Qadam 4 — Extract: (6, D)
D visited qilinadi.
Qo'shnilar:
A: 6 + 6 = 12 > dist[A]=0 → yangilanmaydi
E: 6 + 5 = 11 > dist[E]=10 → yangilanmaydi
PQ: [(6, F), (10, E)]
Qadam 5 — Extract: (6, F)
F visited qilinadi.
Qo'shnilar:
C: 6 + 1 = 7 > dist[C]=5 → yangilanmaydi
E: 6 + 4 = 10 = dist[E]=10 → teng, yangilanmaydi
PQ: [(10, E)]
Qadam 6 — Extract: (10, E)
E visited qilinadi. Qo'shnilari yaxshilanmaydi.
PQ: []
Yakuniy natija:
Adan Fga eng qisqa yo'l: A → B → C → F = 2 + 3 + 1 = 6.
Path reconstruction
Faqat masofalar emas, yo'lning o'zi ham kerak bo'lsa, har vertex qaysi vertexdan ochilganini saqlaymiz:
FUNCTION DIJKSTRA_WITH_PATH(graph, start)
dist = barcha vertexlar uchun INFINITY
dist[start] = 0
parent = barcha vertexlar uchun NULL
priority_queue = [(0, start)]
visited = bo'sh set
WHILE priority_queue bo'sh emas
(current_dist, current) = priority_queue.EXTRACT_MIN()
IF current visited ichida bo'lsa
CONTINUE
visited ga current ni qo'sh
FOR har bir (neighbor, weight) graph.adjacency[current] ichida
new_dist = dist[current] + weight
IF new_dist < dist[neighbor]
dist[neighbor] = new_dist
parent[neighbor] = current
priority_queue.INSERT((new_dist, neighbor))
RETURN dist, parent
FUNCTION GET_PATH(parent, target)
path = bo'sh list
v = target
WHILE v ≠ NULL
path ga v ni qo'sh
v = parent[v]
RETURN path ni teskari tartibda
Vaqt va xotira murakkabligi
Murakkablik priority queue implementatsiyasiga bog'liq:
| Priority queue | Vaqt | Eslatma |
|---|---|---|
| Binary heap | O((V + E) log V) |
Amalda keng tarqalgan |
| Fibonacci heap | O(V log V + E) |
Nazariy optimal, amalda murakkab |
| Sodda array | O(V²) |
Dense grafda ba'zan mos |
Binary heap bilan: har vertex bir marta extracted — jami V marta O(log V). Har edge uchun bir marta relaxation va insert — jami E marta O(log V). Jami: O((V + E) log V).
Dense grafda E ≈ V² bo'lsa, binary heap bilan O(V² log V). Bunday holda sodda array — har qadamda barcha vertexlarni ko'rish — O(V²) bo'lib yaxshiroq bo'lishi mumkin.
Xotira: O(V + E) — adjacency list, dist array, visited set, priority queue.
Nima uchun Dijkstra manfiy edge bilan ishlamaydi
Dijkstraning asosi: vertex birinchi marta priority queue'dan chiqarilganda uning masofasi final — endi yaxshilanmaydi.
Bu to'g'ri faqat manfiy bo'lmagan og'irliklar bilan. Manfiy edge bo'lsa, keyinchalik allaqachon "final" deb belgilangan vertex uchun qo'shimcha manfiy og'irlik orqali yaxshiroq yo'l topilishi mumkin. Dijkstra bu yangilanishni e'tiborsiz qoldiradi va noto'g'ri natija beradi.
Misol:
A → C= 2A → B → C= 4 + (−3) = 1
Dijkstra Cni dist=2 bilan visited qilib oladi, keyin B → C = 1 yaxshiroq bo'lsa ham e'tiborsiz qoladi. Noto'g'ri natija: dist[C] = 2.
To'g'ri javob: 1. Manfiy edge uchun Bellman-Ford algoritmi ishlatiladi — u barcha edge'larni V − 1 marta relax qiladi va manfiy cycle'larni ham aniqlaydi.
Real qo'llanishlar
Navigatsiya. GPS navigatori shaharlar orasidagi eng tez yoki eng qisqa marshrutni Dijkstra asosida topadi. Qirralar vaqt, masofa yoki muqobil transport narxi bo'lishi mumkin.
Tarmoq marshrutlash. Internet routerlari paketlarni qaysi yo'l orqali yuborishni aniqlashda Dijkstrani ishlatadi. OSPF (Open Shortest Path First) protokoli shunga asoslanadi.
O'yin artificial intelligence. Xaritadagi NPC eng qisqa yo'lni hisoblashda Dijkstra yoki A* (Dijkstraning heuristic bilan kengaytmasi) ishlatiladi.
Dependency tarmoqlari. Paket menejeri dependencylar orasidagi minimal narxli o'rnatish tartibini topadi.
Keng tarqalgan xatolar
Manfiy edge mavjud grafda ishlatish
Dijkstra bu holat uchun mo'ljallanmagan. Kirish grafida manfiy edge borligini tekshirib, kerak bo'lsa Bellman-Ford ishlatiladi.
Priority queue o'rniga oddiy queue ishlatish
BFS kabi oddiy queue bilan Dijkstra yozilsa, "eng yaqin birinchi" invarianti buziladi. Natija noto'g'ri bo'ladi.
Eskirgan priority queue yozuvlarini e'tiborsiz qoldirmaslik
Vertex bir necha marta priority queue'ga tushishi mumkin. visited tekshiruvi eskirgan yozuvlarni o'tkazib yuborish uchun muhim. Unda bo'lmasa, bir vertex bir necha marta qayta ishlanadi.
Disconnected grafda unreachable vertex
Manbadan yetib bo'lmaydigan vertex INFINITY masofada qoladi. Bu normal holat — "yo'l yo'q" degani. INFINITYni haqiqiy masofa sifatida ishlatib qo'ymaslik kerak.
Vaqt murakkabligi jadvali
| Holat | Vaqt | Eslatma |
|---|---|---|
| Binary heap, sparse graf | O((V + E) log V) |
Umumiy holat |
| Sodda array, dense graf | O(V²) |
E ≈ V² bo'lsa |
| Fibonacci heap | O(V log V + E) |
Nazariy minimal |
Qachon ishlatish kerak?
- Manfiy bo'lmagan og'irliklarda bitta manbadan barcha vertexlargacha shortest path
- Navigatsiya, tarmoq, o'yin pathfinding kabi real vaqt talab qiluvchi masalalar
- Ko'p shortest-path so'rovi bir grafdagi bitta manbadan bo'lsa (bir marta hisob, ko'p so'rov)
Qachon ishlatmaslik kerak?
- Manfiy edge bo'lsa — Bellman-Ford yoki SPFA
- Barcha juftliklar orasidagi shortest path kerak bo'lsa — Floyd-Warshall
O(V³)ammo barcha juftlarni bir yo'la beradi - Og'irliksiz grafda — BFS yetarli,
O(V + E)va kodi sodda - Maqsad berilganda erta to'xtatish va heuristic kerak bo'lsa — A* algoritmiga o'tish mumkin
Xulosa
Dijkstra manfiy bo'lmagan og'irliklarda bitta manbadan barcha boshqa vertexlargacha eng qisqa pathni greedy yondashuv va priority queue yordamida topadi.
Har qadamda hozircha ma'lum eng yaqin vertexdan davom etib, uning qo'shnilariga masofalarni relax qiladi. Vertex birinchi marta priority queue'dan chiqarilganda uning masofasi final — bu kafolat manfiy bo'lmagan og'irliklar bilan ishlaydi.
Binary heap bilan O((V + E) log V) vaqt murakkabligi ko'pchilik amaliy masalalar uchun yetarli. Manfiy edge — Dijkstraning asosiy cheklovi: bunday holat uchun Bellman-Ford ishlatiladi.