本文主要是介绍迪克斯特拉(Dijkstra)算法 单源最短路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
输入
第一行输入定点数N
第i行 s(起结点) k(与起结点相连的组数) g(终结点) v(权值)
#include<stdio.h>
#include<string.h>
#define max 1000
#define INF 999999
int m[max][max]; //m[s][g]中记录s到g的边的权值
int d[max]; //d[v]记录起点到v边的权值
int visit[max]; //visit[v]记录v的访问状态
int n;
void dijkstra()
{d[0]=0;while(1){int min=INF,u;int flag=1;for(int i=0;i<n;i++){if(d[i]<min&&visit[i]==0){min=d[i];u=i;flag=0;}}visit[u]=1;if(flag) break;for(int i=0;i<n;i++){if(d[i]>(d[u]+m[u][i])){if(visit[i]==0){d[i]=d[u]+m[u][i];}}}}for(int i=0;i<n;i++){printf("0到%d的最短距离为:%d\n",i,d[i]);}
}
int main()
{while(scanf("%d",&n)!=EOF){memset(visit,0,sizeof(visit));for(int i=0;i<n;i++){for(int j=0;j<n;j++){m[i][j]=INF;}d[i]=INF;}int t=n;while(t--){int s,m1,g,v;scanf("%d%d",&s,&m1);for(int i=0;i<m1;i++){scanf("%d%d",&g,&v);m[s][g]=v;}}dijkstra();}return 0;
}
这篇关于迪克斯特拉(Dijkstra)算法 单源最短路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!