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

Z时代
2024-01-10
分类：IT

某个源点到其余各顶点的最短路径

这个算法最开始心里怕怕的，不知道为什么，花了好长时间弄懂了，也写了一遍，又遇到时还是出错了，今天再次写它，心里没那么怕了，耐心研究，懂了之后会好开心的，哈哈

Dijkstra算法：

图G

如图：若要求从顶点1到其余各顶点的最短路径，该咋求；

迪杰斯特拉提出“按最短路径长度递增的次序”产生最短路径。

首先，在所有的这些最短路径中，长度最短的这条路径必定只有一条弧，且它的权值是从源点出发的所有弧上权的最小值，例如：在图G中，从源点1出发有3条弧，其中以弧（1，2）的权值为最小，因此，（1，2）不仅是1到2的一条最短路径，并且它可能是源点到其它各个终点的最短路径中的一条子路径。

其次，第二条长度次短的最短路径只可能有两种情况：①它或者只含一条从源点出发的弧且弧上的权值大于已求得最短路径的那条弧的权值，但小于其他从源点出发的弧上的权值②它或者是一条只经过已求得最短路径的顶点的路径。

例如图G中，从1到其他各点。过程中，用d[i]保存从1到i的的最短路径（过程会变化），初值为：若源点到该源点有弧，则为权值，否则初始化为无穷大，每求得一条到达某个终点i的最短路径，就继续检查是否存在以此路径为子路径的到达其他点的最短路径，若存在，判断其长度是否比当前求得的路径长度短，若短，就更新为更短的长度。

如图G中，求得到2的最短路径d[2]为10，就把d[2]作为与2相连的到其他点的子路径继续检查，得到到3的最短路径为d[2]+50=60

过程：

（1）.令S={1}，S集合中表示已经找到最短路径的结点，开始时1为源点，并设定d[i]的初始值为：d[i]=(1,i),

（2）.求出到j点的最短路径，j点为不在S集合中的某点

d[j]=min{d[i]}

（3）.判断所有没在S集合中的顶点k，若d[k]>d[j]+(j,k)则修改d[k]的值为：

d[k]=d[j]+(j,k)

（4）.重复（2）.（3）操作共n-1次，每次操作，在（2）得到一个到

某点的最短路径。

有向图求最短路径


#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;
}

无向图求最短路径

无向图也是相同思路：在构造邻接矩阵时考虑对称就行。

无向图求最短路径且有路径输出

在求最短路的过程中，最短路①它或者是从源点出发的弧②它或者是一条经过已到其他最短路径的顶点的路径。

建立一个新的结构体类型path，该类型变量d表示到达某点的最短路径距离，该类型变量pre表示该最短路径是经过哪个点传过来的


#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;
}