Dijkstra算法模板

Dijkstra求最短路径模板:

void Dijkstra(int v){
	/*相关数组置零*/
	fill(vis,vis+maxn,false);
	fill(d,d+maxn,INF);
	……
	/*相关元素置初值*/
	d[v]=0;
	……
	//以下大部分相同
	for(int i=0;i<N;i++){
		int u=-1,min=INF;
		for(int j=0;j<N;j++){
			if(vis[j]==false&&d[j]<min){
				u=j;
				min=d[j];
			}
		}
		if(u==-1) return ;
		vis[u]=true;
		for(int j=0;j<N;j++){
			if(vis[j]==false&&G[u][j]!=INF){
				if(d[u]+G[u][j]<d[j]){
					/*相关变量 覆盖 操作*/
					d[j]=d[u]+G[u][j];
					……
				}
				else if(d[u]+G[u][j]==d[j]){
					/*相关变量 累加 操作*/
					……
				}
			}
		}
	}
}

关于第二标尺:
可以在Dijkstra算法中同时考虑,或者在Dijkstra算法中保存最短路径,再进行DFS计算第二标尺。

#参考《算法笔记》第十章

上一篇:图的最短路与最小生成树


下一篇:暑假 - Summer Vacation - Dijkstra & DP