Note de curs, clasele 11-12, 23 ianuarie 2014

From Algopedia
Revision as of 16:38, 22 January 2014 by Cata (talk | contribs) (→‎Probleme)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Distanțe minime în grafuri (de la o sursă unică)

Algoritmul lui Dijkstra

Nu vom insista pe acest algoritm decât dacă este nevoie. Dar îi vom studia complexitatea, implementările posibile și limitările.

Care este complexitatea algoritmului? Știm că algoritmul lui Dijkstra vizitează fiecare nod o singură dată și relaxează muchiile care ies din acesta. Așadar, complexitatea totală este O(n * alegere(n) + m * relaxare(n)), unde alegere și relaxare sunt, respectiv, costul de alegere a următorului nod și costul relaxării unei muchii.

  • Dacă stocăm pur și simplu un vector caracteristic al nodurilor vizitate / nevizitate, atunci relaxarea unei muchii se face în O(1), iar alegerea următorului nod în O(n). Complexitatea totală este O(n2 + m) = O(n2).
  • Dacă creăm un heap cu nodurile încă nevizitate, atunci atât alegerea, cât și relaxarea rulează în O(log n), căci necesită operații pe heap. Complexitatea totală este O((m + n) log n) = O(m log n).
  • Putem folosi un heap Fibonacci, care ne permite relaxarea în O(1) și o complexitate totală O(m + n log n). Din păcate, heapurile Fibonacci sunt dificil de implementat.

Remarcăm că, în funcție de n, oricare din primele două implementări poate fi de preferat. Pentru grafuri dese, unde m = O(n2), algoritmul cu vector este preferabil!

Mai precizăm și că implementarea cu heap nu este banală. Trebuie să păstrăm în heap distanțele (curente) de la s la fiecare nod v încă nevizitat. În plus, însă, avem nevoie să creăm niște legături:

  • Pentru extragerea nodului cu distanța minimă, trebuie să cunoaștem cel puțin nodul corespunzător distanței din vârful heapului.
  • După cel extragem minimul din heap, vom dori să reorganizăm heapul, inclusiv să aflăm următorul nod ajuns la vârf.
  • În general, deci, trebuie să știm nodul corespunzător fiecărei distanțe din heap.
  • La vizitarea unui nod u sunt relaxate toate muchiile care ies din u. Potențial, toți vecinii lui u își vor micșora distanța.
  • Avem deci nevoie și de legătura inversă, de la fiecare nod către locul său în heap.

Ce structură de date propuneți? Câtă memorie necesită un graf cu n noduri și m muchii?

Generalități despre distanțele minime

  • Dacă o cale uv oferă distanța minimă între u și v, atunci ea oferă distanța minimă și între oricare două noduri de pe acea cale.
  • Vectorul de părinți π este un arbore cu rădăcina în s care acoperă toate nodurile accesibile din s.
  • Operația de relaxare a unei muchii este generală și o vom revedea și în alți algoritmi.
  • d sunt estimările curente pe parcursul rulării algoritmilor.
  • δ sunt distanțele optime (teoretic).
  • La orice moment, d[v] ≥ δ[v]. Când, prin descreșterea lui d[v], obținem d[v] = δ[v], valoarea lui d[v] nu se mai modifică.
  • Dacă există o cale de cost minim suv și dacă d[u] = δ[u], atunci după relaxarea muchiei (u, v) vom avea d[v] = δ[v].
  • Fie o cale minimă v0, v1, ..., vk unde s = v0. Dacă aceste muchii sunt relaxate în ordine, de la v0 la vk, atunci în final d[vk] = δ[vk].

Muchii de cost negativ

Algoritmul lui Dijkstra funcționează corect numai când toate muchiile sunt nenegative. De ce? Ce pas din algoritm depinde de această condiție? Dați un exemplu de graf cu muchii negative în care algoritmul lui Dijkstra produce rezultate greșite.

Prezența muchiilor negative poate să facă nedefinită problema distanțelor minime. Dacă există un ciclu de lungime negativă pe orice cale de la s la v, atunci prin convenție δ(s', v) = -∞, căci pe drumul de la s la v putem repeta acel ciclu de oricâte ori.

Algoritmul Bellman-Ford funcționează și atunci când graful conține muchii negative, cu condiția să nu existe cicluri negative accesibile din s.

Algoritmul Bellman-Ford

BellmanFord() {
  init();
  for (i = 0; i < n - 1; i++) {
    for (int j = 0; j < e; j++) {
      relaxează(muchie[j]);
    }
  }

  // Important! Vedem dacă informațiile calculate mai sus pot fi crezute.
  for (int j = 0; j < e; j++) {
    if (d[muchie[j].v] > d[muchie[j].u] + muchie[j].cost) {
      return false;
    }
  }
  
  return true;
}

Observăm că algoritmul returnează true sau false pentru a indica dacă vectorul d este corect. Dacă algoritmul depistează cicluri negative, el returnează false.

Idee de demonstrație:

Partea „constructivă a algoritmului” relaxează muchii. Presupunând că graful nu conține cicluri negative, cele mai scurte căi nu pot depăși n - 1 muchii. Întrucât la fiecare iterație algoritmul relaxează toate cele m muchii, rezultă că muchiile de pe orice cale de lungime minimă sunt relaxate în ordine de la s către nodul final (posibil și în multe alte ordini). Ca urmare, d[v] = δ[v] pentru toate nodurile.

Presupunând că graful nu conține cicluri negative, trebuie să arătăm și că algoritmul returnează true. Prin inegalitatea triunghiului, pentru orice muchie (u, v), avem d[v] ≤ d[u] + cost(u,v), deci algoritmul nu are motive să returneze false.

Dacă graful conține cicluri negative, să demonstrăm că algoritmul returnează false. Prin absurd, să presupunem că nu ar fi așa. Fie ciclul v0, v1, ..., vk unde vk = v0. Din suma inegalității triunghiului de-a lungul ciclului rezultă că costul ciclului este nenegativ, ceea ce este o contradicție.

În mod evident, algoritmul Bellman-Ford are complexitate O(m * n).

Îmbunătățiri

Dacă la o iterație întreagă (a lui i), distanțele nu se mai modifică, atunci algoritmul se poate opri prematur. Care este complexitatea lui?

Dacă graful este aciclic, algoritmul se reduce la o sortare topologică. Cum? Care este complexitatea lui?

Putem folosi o coadă pentru ca, la fiecare iterație a lui i, să eliminăm unele muchii care nu au șanse să schimbe vectorul d. Cum?

Probleme

Teme de gândire

Cum găsim un ciclu negativ, dacă doar asta ne interesează? Putem cu o simplă parcurgere DFS? Dați o schiță de demonstrație sau un contraexemplu.

Dacă algoritmul Bellman-Ford returnează false, care este, concret, ciclul de cost negativ pe care l-a găsit?