Dijkstra算法模板

本文主要是介绍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计算第二标尺。

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

这篇关于Dijkstra算法模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！