Algoritmul lui Dijkstra
Ce este si ce face acest algoritm?
Algoritmul lui Dijkstra este un algoritm foarte popular in Teoria Grafurilor. Acesta determina lungimea cea mai scurta de la un nod de start “N” la toate celalalte noduri ale grafului. O mica precizare foarte importanta este faptul ca algoritmul lui Dijkstra functioneaza numai pe grafurile orientate (adica cele “cu un singur sens”). De asemenea, fiecare muchie a grafului trebuie sa aiba atasat un cost.
Daca doresti sa determini drumul minim de la un nod X la un nod Y, si te intereseaza doar ca numarul de noduri sa fie minim, poti atasa fiecarei muchii costul “1”. Drumul de cost minim intre doua noduri obtinut in urma aplicarii algoritmului lui Dijkstra va avea si numar minim de arce din moment ce toate arcele au acelasi cost.
De asemenea, algoritmul lui Dijkstra functioneaza atat pe grafuri conexe cat si pe grafuri neconexe. In caz ca ati uitat ce este “o componenta conexa”, am explicat acest termen in tutorialul despre parcurgerea in adancime (dfs) a unui graf.
Daca vreti sa va jucati putin, ca sa cunoasteti mai bine algoritmul, va recomand aceasta aplicatie web.
Prezentarea generala
Algoritmul lui Dijkstra porneste de la un graf orientat si ponderat (fiecare muchie are un cost). Dupa aceea, programatorul alege nodul de start, iar algoritmul va calcula distanta minima de la nodul de start catre toate celalalte noduri.
Dupa executarea acestui algoritm, rezultatul va fi stocat intr-un vector “distanta” cu “N” elemente. Unde distanta[i] va reprezenta drumul minim de la nodul nostru de start catre nodul cu numarul i.
Problema Dijkstra – infoarena.ro
In continuare vom rezolva impreuna problema Dijkstra de pe infoarena.ro. Varianta pe care urmeaza sa o abordam foloseste o coada de prioritati (heap-uri) pentru a obtine punctajul maxim.
Mare atentie: nodul nostru de start este nodul numarul 1!
Algoritmul lui Dijkstra
- Creeam un vector int D[NMax]; cu semnificatia: D[i] – distanta minima intre nodul de start si nodul numarul i. Initial setam tot vectorul pe infinit, iar D[Start] il vom seta pe 0.
- Marcam toate nodurile ca fiind nevizitate. Si creeam o coada de prioritate (priority queue / heap-uri) ce o vom folosii pentru acest algoritm. Punem nodul de start in coada.
- Luam nodul – cu valoarea D[nod] minima – din coada si il marcam ca vizitat.
- Se actualizeaza distantele minime ale vecinilor nodului curent.
- Eliminam nodul curent din coada
- Se repeta de la punctul 3 pana cand toate nodurile sunt vizitate.
Ce face coada de prioritate / Heap-ul ? Ce rol are?
O coada de prioritate este un tip “special” de coada. Principiul este la fel, poti sa introduci elemente in coada, sa le accesezi si sa le elimini.
Doar ca in acest caz valorile intra si ies din coada in functie de “prioritatea” pe care o au.
Ne vom folosii de urmatoarea “prioritate”. Deoarece trebuie sa accesam tot timpul distanta minima a unui nod (D[i]) din coada, vom folosii aceasta conditie drept un criteriu de extragere a nodurilor din coada.
struct compara { bool operator()(int x, int y) { return D[x] > D[y]; } }; priority_queue<int, vector<int>, compara> Coada;
In primele randuri am declarat o functie care compare distantele a doua noduri x si y. Avem nevoie sa modificam aceasta proprietate a cozii de prioritate pentru a rezolva problema.
priority_queue<> are 3 parametrii:
- Primul paramestru este un obiect care construieste coada. In cazul nostru sunt numere, asa ca am scris int
- Al doilea parametru este structura in care adunam toate obiectele din coada, in cazul nostru: un vector de int-uri
- Ultimul parametru (care este optional) este o functie ce returneaza TRUE sau FALSE in functie de interogarile noastre
Implementarea in C++
/* Tutoriale-Pe.NET - Algoritmul lui Dijkstra * Link: https://tutoriale-pe.net/algoritmul-lui-dijkstra-c/ * Rezolvare infoarena: http://www.infoarena.ro/problema/dijkstra */ #include <iostream> #include <fstream> #include <queue> #include <vector> using namespace std; ifstream fin("dijkstra.in"); ofstream fout("dijkstra.out"); const int NMax = 50005; const int oo = (1 << 30); int N, M; int D[NMax]; bool InCoada[NMax]; vector < pair <int,int> > G[NMax]; struct compara { bool operator()(int x, int y) { return D[x] > D[y]; } }; priority_queue<int, vector<int>, compara> Coada; void Citeste() { fin >> N >> M; for(int i = 1; i <= M; i++) { int x, y, c; fin >> x >> y >> c; G[x].push_back(make_pair(y,c)); } } void Dijkstra(int nodStart) { for(int i = 1; i <= N; i++) D[i] = oo; D[nodStart]=0; Coada.push(nodStart); InCoada[nodStart] = true; while(!Coada.empty()) { int nodCurent = Coada.top(); Coada.pop(); InCoada[nodCurent] = false; for(size_t i = 0; i < G[nodCurent].size(); i++) { int Vecin = G[nodCurent][i].first; int Cost = G[nodCurent][i].second; if(D[nodCurent] + Cost < D[Vecin]) { D[Vecin] = D[nodCurent] + Cost; if(InCoada[Vecin] == false) { Coada.push(Vecin); InCoada[Vecin] = true; } } } } } void Afiseaza() { for(int i = 2; i <= N; i++) { if(D[i] != oo) fout << D[i] << " "; else fout << "0 "; } } int main() { Citeste(); Dijkstra(1); Afiseaza(); }