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