Dijstra--图的最短路径算法
2025-07-03 15:53:44
发布于：浙江
6阅读
0回复
0点赞
--Dijkstra--
流程：
(一) 定义数组: （1）dis(i)：表示原点到点i的最短路径
（2）vis(i)：标记数组
（3）mp(u,v)：邻接表
(二) 使用邻接表mp存图,mp(u,v)=w（(u,v,w):u到v的距离为w）
(三) 初始化dis数组（d[s]=0 原点到自己距离为0，d[2~n]其余设为无穷大 1e9）
(四) 遍历(n-1)次 (最后一个点无法更新，确认已经求出最短路径）
(1)遍历dis,求出与原点距离最近的且未被标记的点k
(2)在vis中标记点k
(3)对与点k相连的点v进行松弛操作
（松弛操作：比较 dis(k)+w 与 dis(v),若dis(k)+w<dis(v)，将dis(v)更新为dis(k)+w）
(五) 输出dis中每个点与原点的距离
代码示例：
//我是头文件
int n,m,s;
int dis[1005];
int vis[1005];
int mp[1005][1005];
int main(){
cin>>n>>m>>s;
while(m--){
int u,v,w;
cin>>u>>v>>w;
int tmp=mp[u][v]?mp[u][v]:1e9;
mp[u][v]=min(tmp,w);
}
for(int i=0;i<=n;i++){
dis[i]=1e9;
}
dis[s]=0;
for(int i=1;i<n;i++){
int u=0;
for(int i=1;i<=n;i++){
if(vis[i]==0 && dis[i]<dis[u])
u=i;
}
vis[u]=1;
for(int i=1;i<=n;i++){
if(mp[u][i]!=0){
int v=i;
int w=mp[u][i];
if(dis[u]+w<dis[v])
dis[v]=dis[u]+w;
}
}
}
for(int i=1;i<=n;i++){
if(dis[i]==1e9)
cout<<-1<<" ";
else
cout<<dis[i]<<" ";
}
return 0;
这里空空如也
有帮助，赞一个