当前位置: 代码迷 >> 综合 >> 最短路之dijkstra
  详细解决方案

最短路之dijkstra

热度:62   发布时间:2024-01-14 21:56:04.0
    #include <stdio.h>int main(){int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值//读入n和m,n表示顶点个数,m表示边的条数scanf("%d %d",&n,&m);//初始化for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j) e[i][j]=0;  else e[i][j]=inf;//读入边for(i=1;i<=m;i++){scanf("%d %d %d",&t1,&t2,&t3);e[t1][t2]=t3;}//初始化dis数组,这里是1号顶点到其余各个顶点的初始路程for(i=1;i<=n;i++)dis[i]=e[1][i];//book数组初始化for(i=1;i<=n;i++)book[i]=0;book[1]=1;//Dijkstra算法核心语句for(i=1;i<=n-1;i++){//找到离1号顶点最近的顶点min=inf;for(j=1;j<=n;j++){if(book[j]==0 && dis[j]<min){min=dis[j];u=j;}}book[u]=1;for(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(i=1;i<=n;i++)printf("%d ",dis[i]);getchar();getchar();return 0;}