Djkstra on sparse graphs

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
970 B
12
Indexable
Never
class weightedGraph {
public:
  int n;
  vector<pair<int,int>>* adjList;

  void addEdge(int a, int b, int weight) {
    adjList[a].push_back(make_pair(b, weight));
    adjList[b].push_back(make_pair(a, weight));
  }

  vector<int> dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> distances(n, INT_MAX);
    distances[start] = 0;
    
    pq.push(make_pair(0, start));
    while(!pq.empty()) {
      auto pair = pq.top();
      int dist = pair.first;
      int next = pair.second;
      pq.pop();

      if(dist > distances[next]) continue;
      for(auto& v : adjList[next]) {
	if((dist + v.second) < distances[v.first]) {
	  distances[v.first] = dist + v.second;
	  pq.push(make_pair(dist + v.second, v.first));
	}
      }
    }

    return distances;
  }
  
  weightedGraph(int nodes) {
    n = nodes;
    adjList = new vector<pair<int,int>>[n];
  }
};