[ shortest path algorithm ] floyd,dijkstra,bellman,spfa 最短路徑模板

Floyd-Warshall:

	int n;
	int d[105][105];
	int g[105][105];
	/*************************
	點數
	答案
	圖，如果兩點間不存在邊則為INF
	*************************/
	inline void floyd(){
	static int i,j,k;
	for(i=0;i<n;++i){
	for(j=0;j<n;++j){
	d[i][j]=g[i][j];
	}
	}
	for(k=0;k<n;++k){
	for(i=0;i<n;++i){
	for(j=0;j<n;++j){
	if(d[i][j]>d[i][k]+d[k][j]){
	d[i][j]=d[i][k]+d[k][j];
	}
	}
	}
	}
	}

view raw Floyd-Warshall.cpp hosted with ❤ by GitHub

Dijkstra:

	const int MAXN=50005;
	const long long INF=0x3f3f3f3f3f3f3f3f;
	typedef pair<long long ,int > PLI;
	typedef pair<int ,long long > PIL;
	int n,m;//點數、邊數
	vector<PIL> g[MAXN];//圖
	long long d[MAXN];//答案
	inline bool dijkstra(int from,int to){
	priority_queue<PLI,vector<PLI>,greater<PLI> >q;
	for(int i=1;i<=n;++i)d[i]=INF;
	d[from]=0;
	q.push(make_pair(d[from],from));
	while(q.size()){
	PLI u=q.top();
	q.pop();
	int x=u.second;
	if(d[x]<u.first)continue;
	for(size_t i=0;i<g[x].size();++i){
	if(d[g[x][i].first]>d[x]+g[x][i].second){
	d[g[x][i].first]=d[x]+g[x][i].second;
	q.push(make_pair(d[g[x][i].first],g[x][i].first));
	}
	}
	}
	return d[to]==INF?0:1;//有/無解
	}

view raw Dijkstra.cpp hosted with ❤ by GitHub

Bellman-Ford:

	#define x first
	#define y second
	const long long INF=0x3f3f3f3f3f3f3f3f;
	const int MAXN=1005,MAXM=100005;
	int n,m;//點、邊的個數
	pair<pair<int,int > ,int > e[MAXM];//所有邊
	long long d[MAXN];//答案
	int bellman(int from,int to){
	for(int i=0;i<n;++i)d[i]=INF;
	d[from]=0;
	for(int t=1;t<=n;++t){
	bool fix=0;
	for(int i=0;i<m;++i){
	if(d[e[i].x.x]!=INF&&d[e[i].x.y]>d[e[i].x.x]+e[i].y){
	if(e[i].x.y==to&&t==n)return -1;//從from到to會經過負環
	d[e[i].x.y]=d[e[i].x.x]+e[i].y;
	fix=1;
	}
	}
	if(!fix)break;
	}
	return d[to]!=INF;//有/無解
	}

view raw Bellman-Ford.cpp hosted with ❤ by GitHub

SPFA:

	const int MAXN=50005;
	const long long INF=0x3f3f3f3f3f3f3f3f;
	typedef pair<int,long long > PIL;
	int n,m;//點數、邊數
	vector<PIL> g[MAXN];//圖
	long long d[MAXN];//答案
	bool inq[MAXN];//是否在queue裡面
	int inq_cnt[MAXN];//進queue的次數
	inline int spfa(int from,int to){
	queue<int > q;
	for(int i=1;i<=n;++i)d[i]=INF,inq[i]=inq_cnt[i]=0;
	d[from]=0;
	inq[from]=inq_cnt[from]=1;
	q.push(from);
	while(q.size()){
	int o=q.front();
	q.pop();
	if(inq_cnt[o]>n)return -1;//存在負環
	inq[o]=0;
	for(size_t i=0;i<g[o].size();++i){
	if(d[g[o][i].first]>d[o]+g[o][i].second){
	d[g[o][i].first]=d[o]+g[o][i].second;
	if(!inq[g[o][i].first]){
	inq[g[o][i].first]=1;
	++inq_cnt[g[o][i].first];
	q.push(g[o][i].first);
	}
	}
	}
	}
	return d[to]!=INF;//有/無解
	}

view raw SPFA.cpp hosted with ❤ by GitHub