Cây khung nhỏ nhất - Thuật toán Prim

Cây khung nhỏ nhất - Thuật toán Prim

Độ phức tạp: O(E * logV)


#include <bits/stdc++.h>
using namespace std;

const int INT_MAX = 1e9; typedef pair<int, int> pii;

// input
vector<vector<pii> > adj;

// output
vector<int> pre;


long long Prim() {
  int n = adj.size();
  pre.assign(n, -1);
  vector<bool> visited(n);
  vector<int> dist(n, INT_MAX);
  dist[0] = 0;

  priority_queue<pii, vector<pii> , greater<pii> > q;
  q.push(make_pair(0, 0));

  long long res = 0;

  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    
    if (visited[u]) continue;

    visited[u] = true;
    res += d;

    for (int i = 0; i < (int) adj[u].size(); i++) {
      int v = adj[u][i].first;

      if (visited[v]) continue;

      int nprio = g[u][i].second;
      if (dist[v] > nprio) {
        dist[v] = nprio;
        pred[v] = u;
        q.push(make_pair(nprio, v));
      }
    }
  }

  return res;
}


int main() {
  adj.resize(3);
  adj[0].push_back(make_pair(1, 10));
  adj[1].push_back(make_pair(0, 10));
  adj[1].push_back(make_pair(2, 10));
  adj[2].push_back(make_pair(1, 10));
  adj[2].push_back(make_pair(0, 5));
  adj[0].push_back(make_pair(2, 5));

  long long res = Prim();
  cout << res << endl;
}

Đường đi ngắn nhất. Thuật toán Dijkstra's với priority_queue hay set trong

Thuật toán Dijkstra 

Độ phức tạp: O(E.logV)

#include <bits/stdc++.h>
using namespace std;

const int INT_MAX = 1e9;
typedef pair<int, int> pii;

// input
vector<vector<pii> > adj;

// output
vector<int> dist, pre;
Thuật toán Dijkstra với priority_queue

void Dijkstra(int s) {
  // Khoi tao
  int n = adj.size();
  dist.assign(n, INT_MAX);
  dist[s] = 0;
  pre.assign(n, -1);

  priority_queue<pii, vector<pii> , greater<pii> > q;
  q.push(make_pair(0, s));

  // Lap
  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();

    if (d != dist[u]) continue;

    for (int i=0; i<(int) adj[u].size(); i++) {
      int v = adj[u][i].first;
      int uv = adj[u][i].second;
      

      if (dist[v] > d+uv) {
        dist[v] = d+uv;
        pre[v] = u;
        q.push(make_pair(dist[v], v));      
      }
    }
  }
}



Thuật toán Dijkstra với set

void Dijkstra2(int s) {
  // Khoi tao  
  int n = adj.size();  
  dist.assign(n, INT_MAX);  
  dist[s] = 0;  
  pre.assign(n, -1);  

  set<pii> q;  
  q.insert(make_pair(0, s));  

  // Lap  
  while (!q.empty()) {    
    int u = q.begin()->second;

    q.erase(q.begin()); 
   
    for (int i=0; i<(int) adj[u].size(); i++) {      
      int v = adj[u][i].first;      
      int uv = adj[u][i].second;     

      if (dist[v] > dist[u]+uv) {        
        q.erase(make_pair(dist[v], v));        
        dist[v] = ndist[u]+uv;        
        pre[v] = u;        
        q.insert(make_pair(dist[v], v));      
      }    
    }
  }
}


int main() {
  adj.resize(2);
  adj[0].push_back(make_pair(1, 10));
  adj[1].push_back(make_pair(2, -5));
  adj[0].push_back(make_pair(2, 8));

  Dijkstra(0);

  for (int i = 0; i < dist.size(); i++)  cout << dist[i] << endl;
}