1.最短路算法
原题链接：102625.1.最短路算法
2026-02-04 14:57:32
发布于：江苏
14阅读
0回复
0点赞
**Dijkstra 核心代码**:
for(int i=1;i<=n;i++){
int u=0;
for(int j=1;j<=n;j++){
if(!vis[j] && dis[j] < dis[u]) u = j;
}
vis[u]= 1;
for(int j=1;j<=n;j++){
if(e[u][j]){
int v=j;
int w = e[u][j];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
}
**Bellman-Ford (SPFA) 核心代码**:
while(q.size()){
int u=q.front();
q.pop();
vis[u] = 0;
for(int i=1;i<=n;i++){
if(d[i]>d[u]+g[u][i]){
d[i] = d[u]+g[u][i];
if(vis[i]==0){
vis[i]=1;
q.push(i);
}
}
}
}
**Floyd 核心代码** :
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
}
}
这里空空如也
有帮助，赞一个