Dijkstra
(lib/graph/dijkstra.hpp)

• View this file on GitHub
• Last update: 2021-11-09 20:40:43+09:00
• Include: #include "lib/graph/dijkstra.hpp"

説明

• 負辺のない g: Graph に対して、(頂点 s: int から各頂点への最短パスの長さ: vector, 前の頂点: vector)を求める

時間計算量

• O(E log V)

Verified with

• test/graph/dijkstra.test.cpp

Code

#pragma once
struct status{
	lint dist;
	status(lint n){
		if(!n)dist = 0; //initial
		else dist = linf; //infinity
	}
};
constexpr bool operator<(const status& lhs, const status& rhs){
	return lhs.dist<rhs.dist;
}
status operator+(status cur, length cost){
	cur.dist += cost;
	return cur;
}

pair<vector<status>, vector<int>> dijkstra(Graph g, int s, vector<length>&cost){
	vector<int> prv(g.size());
	vector<status> d(g.size(), linf);
	using cont = pair<status, int>;
	priority_queue<cont, vector<cont>, greater<cont> > q;

	d[s] = 0; q.push({ 0,s });
	while(q.size()){
		status cd = q.top().first;
		int cv = q.top().second;
		q.pop();
		if(d[cv]<cd)continue;
		for(edge& e:g[cv])if(cd+cost[e.id]<d[e.to]){
			d[e.to] = cd+cost[e.id];
			prv[e.to] = cv;
			q.push({ d[e.to],e.to });
		}
	}
	return { d,prv };
}

/*
* @title Dijkstra
*/

#line 2 "lib/graph/dijkstra.hpp"
struct status{
	lint dist;
	status(lint n){
		if(!n)dist = 0; //initial
		else dist = linf; //infinity
	}
};
constexpr bool operator<(const status& lhs, const status& rhs){
	return lhs.dist<rhs.dist;
}
status operator+(status cur, length cost){
	cur.dist += cost;
	return cur;
}

pair<vector<status>, vector<int>> dijkstra(Graph g, int s, vector<length>&cost){
	vector<int> prv(g.size());
	vector<status> d(g.size(), linf);
	using cont = pair<status, int>;
	priority_queue<cont, vector<cont>, greater<cont> > q;

	d[s] = 0; q.push({ 0,s });
	while(q.size()){
		status cd = q.top().first;
		int cv = q.top().second;
		q.pop();
		if(d[cv]<cd)continue;
		for(edge& e:g[cv])if(cd+cost[e.id]<d[e.to]){
			d[e.to] = cd+cost[e.id];
			prv[e.to] = cv;
			q.push({ d[e.to],e.to });
		}
	}
	return { d,prv };
}

/*
* @title Dijkstra
*/

Back to top page