Dijkstra - 详解 - Acmer - (转载保存) - 讲的非常好

不念不忘少年蓝@ 2022-05-17 00:39 151阅读 0赞

### 原文章： https://blog.csdn.net/tianhaobing/article/details/65443049  **最短路径之Dijkstra算法(看到i,j,k三个变量可以理解为需要三个for循环，方便记忆)** ###

本节来学习指定一个点(源点)到其余各个顶点的最短路径,也称为”单源最短路径”。与上篇的Floyed-Warshall算法一样，这里仍然使用二维数组a来存储顶点之间边的关系。如图:(假设我要求的是1号顶点到其余顶点的最短距离)  
![这里写图片描述][SouthEast]  
当然，我们还需要一个dis数组来存储1号顶点到其余顶点的当前距离，如图:  
![这里写图片描述][SouthEast 1]  
既然是求1号顶点到其余顶点的最短的距离,那么我们就从dis数组中找到一个距离1号顶点的最短距离的顶点。通过dis数组可知，当前距离一号顶点的最短的顶点为2号顶点。所以1号顶点到2号顶点的最短距离为2。为什么呢?因为距离都为整数，所以不可能找到第三个中转点使得1号顶点到2号顶点的距离最短了。只要从1号顶点到中转点，那么他们间的距离已经大于1号到2号顶点的距离了！(值得我们注意的是:并不是说之后只要从dis数组中找到最短的距离，那么就是1号顶点到该点的最短距离了)  
当前我们找到了1号顶点到2号顶点的最短距离为2，那么我们来看看2号顶点有哪些出边呢?由邻接矩阵我们可以知道,2号顶点的出边为3号和4号顶点,我们看看2—->3号这条边能否比直接从1—->3的距离变短呢?也就是说我们来比较dis\[3\]和a\[2\]\[3\]+dis\[2\]谁大谁小。可以知道a\[2\]\[3\]+dis\[2\]小于dis\[3\]所以我们更新当前1号到3号的距离，为5，同理，我们知道1—>4号的距离也可以缩小到8,所以，dis的数组变为:  
![这里写图片描述][SouthEast 2]

然后,我们继续找当前dis数组(除了2号顶点，因为我们已经找过了，所以在代码部分我们可以用一个数组来标记哪些点被找过了)距离1号顶点最短距离的顶点为5号顶点。然后我们看5号顶点有哪些出边，能否使得通过5号顶点使得某些点的距离变得更短。可以知道通过5号顶点可以使得1—>4号的距离缩短为5,1—->6号顶点的距离缩短为7。所以dis数组变为:  
![这里写图片描述][SouthEast 3]  
（5号顶点被用过了，我们就标记5号顶点）  
接下里我们从3，4,6号顶点找距离1号顶点最短的距离,当前为4号顶点,出边为4—>3,4—->6,没找到可以缩短的  
![这里写图片描述][SouthEast 3]  
继续从3,6找当前距离1号顶点最短的点为3，找3的出边，3—>5，dis\[5\]>a\[3\]\[5\]+dis\[3\]，没法缩短。  
![这里写图片描述][SouthEast 3]  
最后找到只剩下6这个顶点，没有出边。所以不dis不变  
![这里写图片描述][SouthEast 3]  
所以由dis数组可知，1号到1~6号的最短距离分别为，0,2,5,5,3,7

讲了这么多，上一波代码:

//这个代码求的是第一个顶点到其他顶点的最短距离
    #include<stdio.h>
    int main()
    {            //采用邻接矩阵来存储图
        int a[100][100],point,i,j,k,number,t1,t2,t3,u,v,min,book[10]={
       0},dis[10];
        //point表示顶点数，number表示边数,t1,t2,t3,表示t1到t2的距离为t3,book数组用来标记哪些点目前是最短的距离,dis数组用来存储第一个顶点到其余顶点的最短距离
        int inf=99999999; //假设这个数表示无穷大
           scanf("%d %d\n",&point,&number);
           for(i=1;i<=point;i++)  //本人习惯数组从1开始，这样可以用a[1]来表示第一个顶点
               for(j=1;j<=point;j++){
                   if(i==j){
                       a[i][j]=0;//初始化，当每个顶点到自身时，距离为0，否则为无穷大
                   }else{
                    a[i][j]=inf;
                   }
               }
                 //开始读入边
               for(i=1;i<=number;i++){
                 scanf("%d %d %d",&t1,&t2,&t3);
                 a[t1][t2]=t3;
               }
    
               for(i=1;i<=point;i++){
                   dis[i]=a[1][i];
               } //存放1号顶点到其余顶点的距离,不可达则为inf（无穷大）
    
        book[1]=1;//标记第一个顶点已经是最短距离
    
        //Dijkstra算法开始
        for(i=1;i<=point-1;i++){
    
              min=inf;
              for(j=1;j<=point;j++){    //求出当前dis数组中离第一个顶点最短的距离的顶点的下标
                  if(book[j]==0 && dis[j]<min){
                        min=dis[j];
                        u=j;//记下这个点的下标
                  }
              } 
    
              book[u]=1;
    
              for(k=1;k<=point;k++){  
                  if(a[u][k]<inf){
                       if(dis[k]>dis[u]+a[u][k]){
                              dis[k]=dis[u]+a[u][k];
                  }
                }
    
              }     //若找到其他途径比从1号顶点直接到目的顶点的距离短，则替换掉
    
    
        }
    
    
        for(i=1;i<=point;i++){
            printf("1号顶点到%d号顶点的最短距离为------>%d\n",i,dis[i]);
        }
    
    
    
    
    return 0;
    }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63

运行结果如图:  
![这里写图片描述][SouthEast 4]

[SouthEast]: /images/20220517/b8713e91f8a447c2bc2b2490636d8c4f.png
[SouthEast 1]: /images/20220517/cbcca7eac9fa431c9bcc1f555c460f11.png
[SouthEast 2]: /images/20220517/0ac97a4900264b7b9c7dc54d7f05df32.png
[SouthEast 3]: /images/20220517/c76c773564d04e3ab7e9d6c9dcdcc650.png
[SouthEast 4]: /images/20220517/275c5ceffb344e30bca6b5c4ffdf3f5b.png