Dijkstra’s Algorithm

• Time : O((v + e)log(v))
• Space : O(v)

c++

#include <vector>
using namespace std;

vector<int> dijkstrasAlgorithm(int start, vector<vector<vector<int>>> edges) {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	vector<int> res(edges.size(), INT_MAX);
	pq.push({0, start});
	
	while(!pq.empty()) {
		auto [c, u] = pq.top(); pq.pop();
		if(c >= res[u]) continue;
		res[u] = c;
		for(auto& edge : edges[u]) {
			int v = edge[0], w = edge[1];
			if(res[v] > w + c)
				pq.push({w + c, v});
		}
	}
	for(auto& c : res)
		if(c == INT_MAX) c = -1;
  return res;
}