Informatică Algoritmi
Algoritmi grafuri drum minim
Algoritmii pentru drumul minim în grafuri calculează cea mai scurtă cale între două noduri. Acești algoritmi sunt fundamentali în informatică, folosiți în rețele, sisteme de navigație și optimizări. Ei se bazează pe structuri de date precum cozi de priorități și matrici.
Algoritmi principali
- Dijkstra Funcționează pentru grafuri cu costuri nenegative, folosind o coadă de priorități pentru a selecta nodul cu distanța minimă la fiecare pas.
- Bellman-Ford Gestionează costuri negative, verificând toate muchiile în mai multe iterații pentru a detecta cicluri negative.
- Floyd-Warshall Calculează drumurile minime între toate perechile de noduri într-un graf, folosind o abordare dinamică cu matrici.
Exemplu numeric Dijkstra
- 1 Pasul 1 Fie un graf cu nodurile A, B, C, muchiile A-B=3, A-C=1, B-C=1. Inițializează distanțe: A=0, B=∞, C=∞.
- 2 Pasul 2 Din A, actualizează: C=1 (A-C), B=3 (A-B). Selectează C ca nod curent.
- 3 Pasul 3 Din C, actualizează: B=2 (A-C-B, 1+1). Drumul minim de la A la B este 2.
Exersează implementarea algoritmilor pe hârtie înainte de cod, pentru a înțelege logica.