堆优化的迪杰斯特拉
迪杰斯特拉算法
- 核心代码
rep(i, 1 , n-1){
int minx = inf;//对于每一次找点，都要找当前最短路的点
int pos;//记录一下是哪个点
//**********优化点A*************
rep(j , 1 , n){
if(!vis[j] && dis[j] < minx){
minx = dis[j];
pos = j;
}
}
//pos顶点加入S集合
vis[pos] = 1;
//************优化点B*****************
//由于pos顶点的进入 对S集合以外的结点 其距离因为pos的加入需要进行更新
rep(k, 1 , n){
if(!vis[k] && dis[k] > dis[pos] + G[pos][k]){
dis[k] = dis[pos] + G[pos][k];
}
}
}re
