Navigatie rutiera
Drumul cel mai scurt sau cel mai rapid intre doua adrese, cu timpi pe segmente de drum.
1. Probleme rezolvate prin drumuri de valoare optima
Un drum optim minimizeaza o functie de cost (distanta, timp, bani, energie, risc) sau maximizeaza o utilitate transformabila in cost. Costurile trebuie definite explicit.
Retele de calculatoare
Rutarea pachetelor pe trasee cu cost, intarziere sau incarcare redusa.
Logistica
Transport intre depozite si clienti pe o retea cu costuri de deplasare.
Roboti mobili
Planificarea deplasarii printre obstacole pe un graf al spatiului liber.
Jocuri video
Deplasarea personajelor pe harta, evitand zonele inaccesibile sau costisitoare.
Retele energetice
Gasirea unei rute de transfer intr-un model de retea, cu costuri definite pe legaturi.
Grafuri de cunostinte
Gasirea unui lant de relatii intre concepte sau entitati, dupa un cost semantic.
Transport public
Traseu cu timp minim, inclusiv asteptari si schimbari intre linii.
Atentie: drumul minim intre doua noduri nu este acelasi lucru cu problema comis-voiajorului sau cu fluxul maxim.
2. Algoritmul lui Dijkstra
Edsger W. Dijkstra , conceput in 1956, publicat in 1959. Determina distantele minime de la un nod de pornire, intr-un graf cu ponderi nenegative.
A = noduri definitive
B = noduri temporare
In afara A si B
Valoarea nodului
Desenele folosesc acelasi graf neorientat. Ponderile muchiilor sunt albe, iar distantele calculate pentru noduri sunt turcoaz.
Pasul 1. Initializarea multimii A
Nodul de pornire S intra in A si primeste valoarea definitiva d(S) = 0. Initial B este vida.
Pasul 2. Formarea multimii B
In B intra vecinii nodurilor din A care nu apartin deja lui A∪B: P si Q. Sunt colorati portocaliu. Pentru un nod din B se examineaza toate muchiile incidente.
Pasul 3. Calculul valorilor temporare
Pentru fiecare v din B se calculeaza d(v) = min [d(u) + w(u,v)], unde u are valoare si este vecin cu v. Initial: d(P) = 0 + 4 = 4 si d(Q) = 0 + 2 = 2. Muchiile din noduri fara valoare nu pot furniza candidati. Roz marcheaza minimul pentru nodul analizat Q.
Pasul 4. Trecerea minimului din B in A
Nodul Q are valoarea temporara minima (2), deci intra in A si valoarea sa devine definitiva. Se reiau pasii 2 si 3: T intra in B; P ramane cu valoarea 4, iar T primeste initial 2 + 6 = 8. Apoi P intra in A si T se recalculeaza: min(8, 4 + 5) = 8.
Pasul 5. Reconstituirea drumului minim
Cand T intra in A, pornim invers de la T. Cautam predecesorii u pentru care d(u) + w(u,T) = d(T). Rezulta Q, deoarece 2 + 6 = 8; apoi S, deoarece 0 + 2 = 2. Drumul minim este S - Q - T, cu valoarea 8. Daca exista egalitati, se pastreaza toate ramurile care satisfac egalitatea.
De ce functioneaza? Cu ponderi nenegative, nicio cale descoperita ulterior nu poate reduce distanta nodului cu valoare minima ales din B. Complexitate: O((V + E) log V) cu liste de adiacenta si heap binar; O(V²) cu selectare liniara a minimului. Acestea sunt desene explicative statice, nu un simulator.
3. Alti algoritmi de drum optim
Algoritmii opereaza pe grafuri; matricea de adiacenta, listele de adiacenta sau listele de muchii sunt moduri de reprezentare, nu clase diferite de probleme.
| Algoritm | Autor / an | Reprezentare uzuala | Ce are special |
|---|---|---|---|
| Bellman-Ford | Bellman (1958), Ford (1956) | Lista de muchii | Permite ponderi negative; detecteaza cicluri negative accesibile. |
| Floyd-Warshall | Floyd (1962), Warshall (1962); antecedent Roy (1959) | Matrice V x V | Drumuri minime intre toate perechile; O(V³). |
| A* | Hart, Nilsson, Raphael (1968) | Graf / grila, liste de vecini | Euristica g+h orienteaza cautarea spre destinatie; optim cu euristica admisibila si implementare corecta. |
| Johnson | Donald B. Johnson (1977) | Liste de muchii si adiacenta | Toate perechile pe grafuri rare, cu ponderi negative dar fara cicluri negative. |
| BFS | Moore (1959); dezvoltari anterioare | Liste de adiacenta / matrice | Drum cu numar minim de muchii in graf neponderat. |
| Bidirectional Dijkstra | Varianta clasica, dezvoltata in timp | Liste de adiacenta | Cauta simultan din start si din destinatie; poate reduce explorarea. |
4. Grafuri mari: pregatirea datelor inainte de cautare
Dijkstra ramane corect pentru costuri nenegative, dar repetarea lui de milioane de ori pe grafuri rutiere uriase poate fi prea lenta. Solutia este sa investim timp si memorie in preprocesare, pentru interogari rapide.
Contraction Hierarchies (CH)
Contracta noduri si adauga scurtaturi care conserva distantele minime. Interogarile exploreaza mult mai putine noduri.
Landmarks + ALT
Precalculeaza distante fata de noduri-reper. Inegalitatea triunghiului furnizeaza euristici puternice pentru A*.
Hub Labeling
Fiecare nod retine un set de noduri-hub si distante. Interogarile combina etichetele celor doua capete.
Partitionare si overlay graphs
Imparte graful in regiuni; construieste un graf rezumat al legaturilor dintre regiuni.
Multilevel Dijkstra / arc flags
Precalculeaza informatii despre regiuni spre care poate conduce un arc pe un drum optim; elimina explorari inutile.
Customizable Route Planning (CRP)
Separa topologia de ponderi: preprocesare structurala, apoi personalizare rapida cand se schimba timpii de deplasare.
Compromis fundamental:
timp de preprocesare + memorie suplimentara versus timp de raspuns. Daca ponderile se modifica des, unele structuri trebuie actualizate sau reconstruite.