Dijkstra算法最短路径的C++实现与输出路径

#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000
//有向图 
int main(){
  int n,m,a,b,v,i,j,min,k;
  scanf("%d%d",&n,&m);//输入n个顶点，m条边 
  int g[n+1][n+1],d[n+1],vis[n+1];//g[i][j]表示i到j的边的权值,vis[i]表示到此顶点的最短路是否已经找到，d[i]当前源点到i顶点的最短路径 
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){ 
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    d[i]=max;  
  }
  for(i=0;i<m;i++){//i到j的边权值储存到g邻接矩阵中,i点到j点无直接相连的边时，g[i][j]=max 
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
  }
  for(i=2;i<=n;i++){
      d[i]=g[1][i]; //初始化源点到i点边权值，之后过程中会发生变化 
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循环n-1次，每循环一次，确定一条最短路，再次循环时这条路就不用考虑了，去寻找下一条最短路 
    min=max;
    for(j=2;j<=n;j++){//寻找下一条当前最短路 
      if(d[j]<min&&vis[j]==0){
       min=d[j];
       k=j;
      }  
    }
    vis[k]=1;//找到了，到k点的路是当前最短路，标记它，根据它寻找下一条最短路 
    for(j=2;j<=n;j++){
      if(d[j]>d[k]+g[k][j]&&vis[j]==0){//经过此k点到达j点的路径是否小于其他到达j点的路径 
        d[j]=d[k]+g[k][j];
      }
    }
  }  
  for(i=2;i<=n;i++){//输出到达个点的最短路径 
    printf("%d\n",d[i]);
  }
  return 0;
}

#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000
typedef struct{ 
  int d;//到达某点的最短路径距离 
  int pre;//该最短路径是经过哪个点传过来的，源点或其他某个点 
}path;
//有向图 
int main(){
  int n,m,a,b,v,i,j,min,k,from;
  scanf("%d%d",&n,&m);//输入n个顶点，m条边 
  int g[n+1][n+1],vis[n+1];//g[i][j]表示i到j的边的权值,vis[i]表示到此顶点的最短路是否已经找到，d[i]当前源点到i顶点的最短路径 
  path to[n+1];//记录当前到某个点的最短路径以及从哪个点传过来的 
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){ 
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    to[i].d=max;  
  }
  for(i=0;i<m;i++){//i到j的边权值储存到g数组中,i点到j点无直接相连的边时，g[i][j]=max 
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
    g[b][a]=v;
  }
  for(i=2;i<=n;i++){
      to[i].d=g[1][i]; //初始化源点到i点边权值，之后过程中会发生变化 
      if(g[1][i]!=max){
       to[i].pre=1; 
      } 
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循环n-1次，每循环一次，确定一条最短路，再次循环时这条路就不用考虑了，去寻找下一条最短路 
    min=max;
    for(j=2;j<=n;j++){//寻找下一条当前最短路 
      if(to[j].d<min&&vis[j]==0){
       min=to[j].d;
       k=j;
      }  
    }
    vis[k]=1;//找到了，到k点的路是当前最短路，标记它，根据它寻找下一条最短路 
    for(j=2;j<=n;j++){
      if(to[j].d>to[k].d+g[k][j]&&vis[j]==0){//经过此k点到达j点的路径是否小于其他到达j点的路径 
        to[j].d=to[k].d+g[k][j];
        to[j].pre=k;//改变j点是谁传来的，现在到j点的最短路径是经过k点的，由j点传来 
      }
    }
  }  
  for(i=2;i<=n;i++){//输出到达个点的最短路径 
    printf("%d ",to[i].d);
    printf("%d ",i);
    j=i;
    while(j!=1){
      j=to[j].pre;
      printf("%d ",j);
    }
    printf("\n");
  }
  return 0;
}