Algoritmul Dijkstra în C++

Când se folosește?

Pentru găsirea drumului minim de la un nod sursă la toate celelalte noduri într-un graf cu costuri pozitive pe muchii.

Implementare cu Priority Queue

Copiază
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
5using namespace std;
6
7typedef pair<int, int> pii;
8const int INF = INT_MAX;
9
10vector<pii> adj[10005];  // adj[u] = {(vecin, cost)}
11int dist[10005];
12int n, m;
13
14void dijkstra(int start) {
15    // Min-heap: (distanță, nod)
16    priority_queue<pii, vector<pii>, greater<pii>> pq;
17    
18    fill(dist, dist + n + 1, INF);
19    dist[start] = 0;
20    pq.push({0, start});
21    
22    while (!pq.empty()) {
23        auto [d, u] = pq.top();
24        pq.pop();
25        
26        // Ignorăm dacă am găsit deja o distanță mai bună
27        if (d > dist[u]) continue;
28        
29        for (auto [v, cost] : adj[u]) {
30            if (dist[u] + cost < dist[v]) {
31                dist[v] = dist[u] + cost;
32                pq.push({dist[v], v});
33            }
34        }
35    }
36}
37
38int main() {
39    cin >> n >> m;
40    
41    for (int i = 0; i < m; i++) {
42        int u, v, cost;
43        cin >> u >> v >> cost;
44        adj[u].push_back({v, cost});
45        adj[v].push_back({u, cost}); // Graf neorientat
46    }
47    
48    int start;
49    cin >> start;
50    dijkstra(start);
51    
52    for (int i = 1; i <= n; i++) {
53        if (dist[i] == INF)
54            cout << "Nod " << i << ": infinit" << endl;
55        else
56            cout << "Nod " << i << ": " << dist[i] << endl;
57    }
58    
59    return 0;
60}

Reconstrucția Drumului

Copiază
1int parinte[10005];
2
3void dijkstraReconstruct(int start) {
4    priority_queue<pii, vector<pii>, greater<pii>> pq;
5    
6    fill(dist, dist + n + 1, INF);
7    fill(parinte, parinte + n + 1, -1);
8    
9    dist[start] = 0;
10    pq.push({0, start});
11    
12    while (!pq.empty()) {
13        auto [d, u] = pq.top();
14        pq.pop();
15        
16        if (d > dist[u]) continue;
17        
18        for (auto [v, cost] : adj[u]) {
19            if (dist[u] + cost < dist[v]) {
20                dist[v] = dist[u] + cost;
21                parinte[v] = u;
22                pq.push({dist[v], v});
23            }
24        }
25    }
26}
27
28void afisareDrum(int dest) {
29    if (dest == -1) return;
30    afisareDrum(parinte[dest]);
31    cout << dest << " ";
32}

Complexitate

• •Cu priority_queue: O((V + E) * log V)
• •Cu set: O((V + E) * log V)
• •Naiv cu array: O(V²)

Limitări

• •Nu funcționează cu costuri negative
• •Pentru costuri negative: folosește Bellman-Ford