Drumuri minime cu costuri

Parcurgerea în lățime găsește drumul cu cele mai puține muchii. Pe o hartă, nu e mereu drumul pe care îl vrei. O autostradă cu trei ieșiri poate fi mai rapidă decât un drum îngust drept peste munte. Când fiecare muchie are lungimea ei, întrebarea devine: care drum are cel mai mic total?

Dă-i fiecărei muchii un număr, costul ei: o lungime în kilometri, un timp în minute, un preț. În intrare, fiecare linie cu o muchie primește un al treilea număr, costul

{"use": "dijkstra-roads"}

Drumurile merg în ambele sensuri, așa că graful e neorientat. De la 0 la 3, cele mai puține muchii sunt două, 0 1 3 sau 0 2 3, și amândouă costă 9. Dar 0 2 1 3 costă 1 + 2 + 5 = 8: o muchie în plus, și mai scurt. Numărarea muchiilor nu mai ajunge

Lista de adiacență ține acum o pereche pentru fiecare vecin: nodul și costul muchiei care duce acolo

{"use": "dijkstra-list"}

Algoritmul lui Dijkstra găsește cea mai mică distanță de la un nod de start la fiecare alt nod. Ține un dist pentru fiecare nod: cel mai scurt drum găsit până acum, sau -1 cât timp nu există niciunul. La început doar startul are unul, 0

Apoi, iar și iar: ia nodul cu cel mai mic dist care nu e încă terminat și marchează-l terminat. Pentru fiecare vecin al lui, vezi dacă drumul prin el e mai scurt decât ce are vecinul. Dacă e, acesta e noul dist al vecinului

{"use": "dijkstra-dist"}

1 primește întâi 4, direct de la 0. Când e luat 2, drumul prin el costă 1 + 2 = 3, așa că 1 scade la 3. 3 primește 9 prin 2, apoi 8 prin 1

Nodul luat nu mai e îmbunătățit niciodată mai târziu. Toate costurile sunt pozitive, așa că orice alt drum până la el ar trece printr-un nod neterminat, al cărui dist e cel puțin la fel de mare, și apoi ar mai adăuga ceva. Tot de aceea algoritmul lui Dijkstra are nevoie de costuri de 0 sau mai mari: o muchie cu cost negativ ar putea face până la urmă un nod terminat mai ieftin

Să găsești cel mai mic nod neterminat e treaba unui heap, cel din lecția despre heap-uri. heapq din Python îl ține într-o listă: heapq.heappush pune o valoare, heapq.heappop o scoate pe cea mai mică. Pune în el perechi, (distanta, nod), și cea mai mică distanță iese prima, pentru că perechile se compară după primul element

import heapq

n, m = map(int, input().split())
vecini = [[] for i in range(n)]
for i in range(m):
    u, v, cost = map(int, input().split())
    vecini[u].append((v, cost))
    vecini[v].append((u, cost))

start = 0
dist = [-1] * n
dist[start] = 0
heap = [(0, start)]
while len(heap) > 0:
    d, u = heapq.heappop(heap)
    if d > dist[u]:
        continue
    for v, cost in vecini[u]:
        if dist[v] == -1 or d + cost < dist[v]:
            dist[v] = d + cost
            heapq.heappush(heap, (dist[v], v))

print(dist)

Rezultat

[0, 3, 1, 8, 11]

Un heap nu poate schimba o valoare aflată deja în el, așa că atunci când 1 scade de la 4 la 3, perechea nouă intră, iar cea veche rămâne. Iese mai târziu, după ce 1 e terminat, iar d > dist[u] o observă și o sare

iau       heap dupa, cea mai mica prima
          (0, 0)
(0, 0)    (1, 2) (4, 1)
(1, 2)    (3, 1) (4, 1) (9, 3)
(3, 1)    (4, 1) (8, 3) (9, 3)
(4, 1)    (8, 3) (9, 3)             veche, sarita
(8, 3)    (9, 3) (11, 4)
(9, 3)    (11, 4)                   veche, sarita
(11, 4)

Misiune: Găsește cele mai scurte drumuri

Citește un graf neorientat cu costuri: pe prima linie n și m, apoi m linii cu câte o muchie, u v c, iar după ele o linie cu nodul de start s
Află cea mai mică distanță de la s la fiecare nod cu algoritmul lui Dijkstra, folosind un heap
Afișează câte o linie pentru fiecare nod, de la 0 la n - 1: nodul, două puncte și distanța lui de la s, sau -1 dacă nu se poate ajunge la el

n este de la 1 la 8, iar nodurile sunt numerotate de la 0 la n - 1. Fiecare cost este un număr întreg de la 1 la 100. Nicio muchie nu unește un nod cu el însuși și nicio pereche de noduri nu e unită de două ori. m poate fi 0

Exemplu

Intrare

Ieșire

Exemplu

Intrare

Ieșire

0: 10
1: 3
2: 2
3: 0
4: -1
5: -1