Qo‘llanma · Dasturlash
shortest-paths
Masalalar tez orada
Nazariya
Vaznli grafda eng qisqa yo‘l. Qaysi algoritm — qirralarga bog‘liq:
| Holat | Algoritm | Murakkablik |
|---|---|---|
| vaznlar bir xil | BFS | O(V + E) |
| vaznlar ≥ 0 | Dijkstra | O(E log V) |
| manfiy vaznlar bor | Bellman–Ford | O(V·E) |
| barcha juftliklar, n ≤ 400 | Floyd–Warshall | O(n³) |
Dijkstra
import heapq
dist = [float("inf")] * n
dist[s] = 0
h = [(0, s)]
while h:
d, v = heapq.heappop(h)
if d > dist[v]:
continue # eskirgan yozuv
for to, w in g[v]:
if d + w < dist[to]:
dist[to] = d + w
heapq.heappush(h, (dist[to], to))
Yo‘lning o‘zini tiklash uchun parent[to] = v saqlang va oxiridan orqaga yuring.
Bu mavzu bo‘yicha masalalar tez orada qo‘shiladi.