Note de curs, clasele 9-10, 15 februarie 2013

Lecție

Drumurile in graf sînt un capitol clasic în algoritmi și structuri de date.

Algoritm și explicație, frontiera de noduri tentative, execuție de mînă.
De ce funcționează? Intuiția? Demonstrație prin reducere la absurd.
Este un algoritm de tip Greedy, foarte asemănător cu algoritmul lui Prim de găsire a arborelui de acoperire minim. Diferența între ei este mică: în acest caz selectăm nodul cel mai apropiat de nodul original, pe cînd în cazul arborelui selectăm cel mai apropiat nod de orice nod care face parte din nodurile deja selectate.
Complexitate: dependentă de structurile de date folosite.
- matrice de adiacență + vector de noduri: O(V²)
- liste de adiacență + vector de noduri: O(V²)
- liste de adiacență + heap: O((E + V) log V)
  - paranteză: cum reprezentăm un graf cu liste de adiacență? Răspuns: în nici un caz cu pointeri si malloc sau new :-)
  - paranteză: cum implementăm un heap? Răspuns: în nici un caz cu pointeri și arbori :-)
    - paranteză la paranteză: cum se creează un heap? Demonstrație complexitate
- liste de adiacență + fibonacci heap: O(E + V log V)
Reconstrucția căii: atunci cînd unui nod i se actualizează distanța vom memora prin ce nod s-a ajuns la el. În final vom reface drumul pornind de la destinație către sursă.
Cazuri particulare:
- muchii de lungime egală: BFS, heap-ul se transformă in coadă. Vezi problema robots la vianuarena.
- BFS pe matrice: Lee. Găsirea ieșirii dintr-un labirint, drumuri minime într-o matrice cu obstacole. Foarte comune la olimpiadă.

Algoritm și explicație.
Cum funcționează? Programare dinamică. Descompunerea în subprobleme drumMinim(i, j, k)
Complexitate: independentă de reprezentarea grafului, este O(n³).
Reconstrucția căii. Vom ține mine o matrice suplimentară în care la fiecare actualizare a distanței minime vom ține minte nodul prin care am actualizat distanța. Reconstrucția căii se face recursiv.