Metode de Reprezentare a Grafurilor: Algoritmul lui Dijkstra 33

---

1. Ce este Algoritmul lui Dijkstra?

Algoritmul Dijkstra este un algoritm de găsire a drumului minim între un nod sursă și toate celelalte noduri dintr-un graf ponderat, orientat sau neorientat. Este eficient pentru grafuri fără greutăți negative.

---

2. Obiectiv

• Determinarea distanțelor minime d[s][v]d[s][v]d[s][v] de la un nod sursă sss la toate celelalte noduri vvv.

---

3. Ideea Algoritmului

Algoritmul funcționează pe baza unui proces iterativ:

1. Nodul sursă sss are distanța inițială 000, iar toate celelalte noduri au distanța ∞\infty∞.
2. Se menține o mulțime de noduri „procesate” (pentru care distanța minimă este stabilită).
3. La fiecare pas, se alege nodul uuu cu cea mai mică distanță din mulțimea de noduri neprocesate.
4. Distanțele către vecinii lui uuu sunt actualizate, dacă trecerea prin uuu oferă un drum mai scurt: d[u][v]=min⁡(d[u][v],d[u]+w(u,v))d[u][v] = \min(d[u][v], d[u] + w(u, v))d[u][v]=min(d[u][v],d[u]+w(u,v)) unde w(u,v)w(u, v)w(u,v) este greutatea muchiei dintre uuu și vvv.
5. Procesul continuă până când toate nodurile au fost procesate.

---

4. Complexitate

• Timp: O((V+E)⋅log⁡(V))O((V + E) \cdot \log(V))O((V+E)⋅log(V)), utilizând o coadă cu priorități (Heap). ∣V∣|V|∣V∣ reprezintă numărul de noduri, iar ∣E∣|E|∣E∣ numărul de muchii.
• Spațiu: O(V+E)O(V + E)O(V+E), pentru stocarea grafului și a vectorilor de distanțe.

---

5. Exemplu

Graf Ponderat

Graful:

1 –(5)–> 2

 |          |

(3)       (2)

 |          |

 v          v

4 <–(4)– 3

• Lista de adiacență (reprezentarea grafului):

1: (2, 5), (4, 3)

2: (3, 2)

3: (4, 4)

4: –

• Rezultate intermediare:

Nod	Distanță de la 1	Nod procesat
1	0	Da
2	5	Da
3	7	Da
4	3	Da

---

6. Implementare în C++

1. Implementare cu Lista de Adiacență și Heap

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

// Structură pentru perechile nod – greutate

typedef pair<int, int> NodGreutate;

void dijkstra(int n, vector<NodGreutate> graful[], int sursa) {

    // Vector pentru distanțe

    vector<int> distanta(n, INT_MAX);

    // Coada cu priorități (min-heap)

    priority_queue<NodGreutate, vector<NodGreutate>, greater<NodGreutate>> minHeap;

    // Inițializarea distanței pentru nodul sursă

    distanta[sursa] = 0;

    minHeap.push({0, sursa}); // (distanță, nod)

    while (!minHeap.empty()) {

        int distCurenta = minHeap.top().first;

        int nodCurent = minHeap.top().second;

        minHeap.pop();

        // Procesăm vecinii nodului curent

        for (auto vecin : graful[nodCurent]) {

            int nodVecin = vecin.first;

            int greutateMuchie = vecin.second;

            // Relaxare: Actualizăm distanța dacă găsim un drum mai scurt

            if (distCurenta + greutateMuchie < distanta[nodVecin]) {

                distanta[nodVecin] = distCurenta + greutateMuchie;

                minHeap.push({distanta[nodVecin], nodVecin});

            }

        }

    }

    // Afișăm distanțele calculate

    cout << „Distanțele minime de la nodul sursă ” << sursa + 1 << „:\n”;

    for (int i = 0; i < n; i++) {

        if (distanta[i] == INT_MAX)

            cout << „Nodul ” << i + 1 << „: INF\n”;

        else

            cout << „Nodul ” << i + 1 << „: ” << distanta[i] << „\n”;

    }

}

int main() {

    int n = 4; // Numărul de noduri

    vector<NodGreutate> graful[4];

    // Adăugare muchii

    graful[0].push_back({1, 5}); // 1 -> 2, cost 5

    graful[0].push_back({3, 3}); // 1 -> 4, cost 3

    graful[1].push_back({2, 2}); // 2 -> 3, cost 2

    graful[2].push_back({3, 4}); // 3 -> 4, cost 4

    int sursa = 0; // Nodul sursă (1)

    dijkstra(n, graful, sursa);

    return 0;

}

---

2. Explicația Codului

1. Lista de adiacență: Reprezintă graful ca o listă de vecini cu greutățile asociate.
2. Min-Heap: Asigură că procesăm mai întâi nodurile cu distanțele cele mai mici.
3. Relaxare: Actualizăm distanțele pentru vecini dacă găsim un drum mai scurt.

---

7. Aplicații ale Algoritmului lui Dijkstra

1. Drumuri minime:
   Utilizat pentru a găsi cele mai scurte drumuri într-un graf ponderat.
2. Rețele de transport:
   Găsirea traseelor optime pentru vehicule între locații.
3. Rețele de calculatoare:
   Determinarea costului minim de transmisie între computere.
4. Jocuri și AI:
   Calcularea drumurilor minime pentru personaje sau obiecte.

---

8. Concluzie

Algoritmul lui Dijkstra este o soluție eficientă și bine-cunoscută pentru determinarea drumurilor minime într-un graf ponderat fără greutăți negative. Este esențial în problemele de optimizare și rezolvarea problemelor din viața reală, precum rețelele de transport sau comunicare.