单源最短路径(Dijkstra算法)
程序员文章站
2024-03-16 13:55:40
...
#include <bits/stdc++.h>
using namespace std;
int main(){
int e[10][10];
int dis[10];
int book[10];
int inf=999999;
int n,m;
cin>>n>>m;
//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)
e[i][j]=0;
else
e[i][j]=inf;
}
}
int t1,t2,t3;
for(int i=0;i<m;i++){
cin>>t1>>t2>>t3;
e[t1][t2]=t3;
}
for(int i=1;i<=n;i++){
dis[i]=e[1][i];
}
for(int i=1;i<=n;i++){
book[i]=0;
}
book[1]=1;
//Dijkstra算法核心语句
int min;
int u = 0;
for(int i=1;i<n;i++){ //确定点为n-1次
min=inf;
for(int j=1;j<=n;j++){ //找出最小边
if(book[j]==0 and dis[j]<min){
min=dis[j];
u=j;
}
}
book[u]=1;
for(int v=1;v<=n;v++){
if(e[u][v]<inf){ //有边
if(dis[v]>dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
}
}
}
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
return 0;
}
/*
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
-----------------
0 1 8 4 13 17
*/
上一篇: 文言文能编程???