单源最短路径(Dijkstra)
Dijkstra 算法基本流程:
1.初始化dist[1] = 0,其节点的dist标记为正无穷大。
2.找出一个未标记的,dist[x]最小的节点x,然后标记节点x。
3.扫描节点x的所有出边(x,y,z),若dist[y]>dist[x]+z,更新dist[y]。
4.重复2-3两个步骤,直到所有节点都被标记。
Dijkstra算法是基于贪心算法,它只适用于所有便都是非负整数的图。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1001;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
void dijkstra(){
memset(dist,0x3f,sizeof(dist));
dist[1] = 0;
for(int i=1;i<=n-1;i++){
int x = 0;
for(int j=1;j<=n;j++){
if(!st[j]&&(dist[j]<dist[x]||x==0)){
x = j;
}
}
st[x] = 1;
for(int j=1;j<=n;j++){
dist[j] = min(dist[j],dist[x] + g[x][j]);
}
}
}
int main(){
cin >> n >> m;
memset(g,0x3f,sizeof(g));
for(int i=1;i<=n;i++) g[i][i] = 0;
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b],c);
}
dijkstra();
for(int i=1;i<=n;i++) cout << dist[i] << endl;
return 0;
}