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计算第二标尺。
#参考《算法笔记》第十章