Dijkstra Algorithm

                                               Resource Link

Dijkstra Algorithm

Dijkstra on sparse graphs

	#include<bits/stdc++.h>
	using namespace std;
	const int INF = 1e9 + 7;
	vector<pair<int,int> > graph[1000];
	vector<int> p,d;
	void dijkstra(int s, int n)
	{
	// int n = graph.size();
	d.assign(n,INF);
	p.assign(n, -1);
	d[s] = 0;
	using pii = pair<int,int>;
	priority_queue<pii, vector<pii>, greater<pii>> PQ;
	PQ.push({0,s});
	while(!PQ.empty()){
	int v = PQ.top().second;
	int d_v = PQ.top().first;
	PQ.pop();
	if(d_v != d[v]) continue;
	for(auto x: graph[v]){
	int to = x.first;
	int len = x.second;
	if(d[v] + len < d[to]){
	d[to] = d[v] + len;
	p[to] = v;
	PQ.push({d[to], to});
	}
	}
	}
	}
	int main()
	{
	int v,e;
	cin >> v >> e;
	for(int i = 0; i < e; i++){
	int u, v, w;
	cin >> u >> v >> w;
	graph[u].push_back({v,w});
	graph[v].push_back({u,w});
	}
	dijkstra(0,v);
	for(int i = 0; i < v; i++){
	cout << d[i]<<endl;
	}
	return 0;
	}
	/**
	9 14
	0 1 4
	0 7 8
	1 2 8
	1 7 11
	2 3 7
	2 8 2
	2 5 4
	3 4 9
	3 5 14
	4 5 10
	5 6 2
	6 7 1
	6 8 6
	7 8 7
	0 4 12 19 21 11 9 8 14.
	*/

view raw Dijkstra.cpp hosted with ❤ by GitHub

Share: