【基础算法】图论——Dijkstra算法

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 101
using namespace std;
int w[N][N],dis[N],vis[N]; //w是边的权重 dis[]从起点到v点的最短路径
//vis代表是否访问过 
int n,m;//n是结点数，m是边数 
void Dijkstra(int x){//求从x到任一点的最短路径 
	memset(dis,INF,sizeof(dis));//dist[]=INF
	dis[x]=0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		int j=0;
		for(int k=1;k<=n;k++){//找最小未被访问的dist[j]
			if(!vis[k]&&dis[k]<=dis[j]){
				j=k;
			}
		}
		vis[j]=1;
		for(int k=1;k<=n;k++){//更新dis[j]
			dis[k]=min(dis[k],dis[j]+w[j][k]);
		}
	}
}
int main(){
	int x,y,v,p;
	cin>>n>>m>>p;//p代表起点 
	memset(w,INF,sizeof(w)) ;
	while(m--){
		cin>>x>>y>>v;
		w[x][y]=w[y][x]=v;
	}
	//从结点p到n的最短路径 
	Dijkstra(p);
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}