643-Dijkstra迪杰斯特拉算法

「爱情、让人受尽委屈。」 2022-09-12 12:50 258阅读 0赞

## Dijkstra迪杰斯特拉算法 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
每个顶点之间的边都带着1个权值，这个权值可以表示任意的花费，距离，时间等等。  
**比如说我们指定一个起始的顶点A，和一个末尾的顶点E， 如果我们要求这2个单元之间的最短路径，** ![在这里插入图片描述][c109f3e243af4415a1e7d26814142bac.png]  
**实际上，它把A-B,A-C,A-D,A-E,A-F的最短路径都算出来了，最后才得到A-E的最短路径是什么**  
通过迪杰斯特拉算法，我们可以知道从起始节点开始，到任意一个节点的最短路径。

## 处理过程 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**迪杰斯特拉算法首先给了我们2个集合**：S集合和U集合  
**迪杰斯特拉算法的核心思想**：计算了起始节点到其他所有节点的最短路径。  
它不计算起始节点到所有节点的最短路径，可能就不知道A-E选择哪条路径是最短的。  
**S集合**：存放已求出最短路径的顶点集合  
**U集合**：存放未确定最短路径的顶点的集合  
![在这里插入图片描述][5dd53552f9884d15948de4090869ac02.png]  
比如说，A-B，B是A的出边，A可以到达B，距离是6，权值是6  
A-D，A不能直接到达D，所以A-D的权值就是无穷大

初始时，S集合只有一个源点，我们当做是A节点，我们以A为起始的顶点，A-A不用做任何的花费，相当于就是已经知道A如何到达A了  
此时，U集合存放的就是：BCDEF  
![在这里插入图片描述][7c5497984a0641d197139d79309767e8.png]  
**当然，我们还有一个辅助的数组**，记录所有节点的当前计算出的最短路径信息  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**因为它在一步一步计算**  
比如说A-B是6  
A-C-B是5  
也就是说A-C-B的权值更小  
**算法要求图中不存在负权边**  
如果存在负权，就代表了其他的意义，成了减法，无法正确表达迪杰斯特拉算法的思想  
迪杰斯特拉算法就是通过权值的和最小来计算最短路径的  
所以，权值都是正数  
**辅助数组的初始化长度：有几个顶点就是多长**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
A-A我们记成INF，也叫做无穷大，A-B是6，A-C是3，A-D是INF，A-E是INF，A-F是INF  
这就表示S集合中的A，已经是计算出来A到所有节点的路径了  
**S集合的初始化是A，然后我们在辅助数组也初始化了A到所有节点的路径**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**这个是初始化操作  
现在，循环5次，计算A到BCDEF**  
首先在遍历U集合，找出当前S集合中的A，到哪个节点的权值是最小的。  
我们就遍历这个辅助数组就可以了，发现是3，对应的是C  
**现在就是找到U集合中权值的最小值，然后把C从U集合移动到S集合当中**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
我们的辅助数组记录的是A到其他节点的目前为止的最短路径信息。  
现在又有一个C进来了。  
现在就有2种可能：A走到C，一种是A直接走到其他所有节点，一种是：A-B的权值是6，说不定呢，把一个新的最小权值的顶点加到S集合当中，A-C-B的权值可能比A-B的权值小，也有可能A-B的权值大于A-C-B的权值  
A-C-D的权值可能比原来A-D的权值更小。  
也就是说。当我们把C加到S集合当中，还没有完事，需要更新一下辅助数组，现在有一个新的顶点进来S了，现在把U集合中的顶点的权值再计算一下，U集合是之前认为的暂时的最短路径，现在有C进来了，要更新一下了。  
现在U集合：BDEF  
**所以我们在辅助数组中更新这几个元素**  
我们看B，A-C是3，C-B是2，3+2=5，这个5比原来A直接到B的6小！  
所以说A-C-B的这个路径是更短的。  
所以，我们把原来的6改为5  
![在这里插入图片描述][a204476d682747f6bbda250b9dfa8117.png]  
然后我们看D，A-C是3，C-D是3，3+3=6，A-C-D是6  
而原来的A-D是INF无穷大，6更短，所以这个INF就被替换为6了  
![在这里插入图片描述][61e2398ded36405294e061b83fecf4f8.png]  
然后我们看E，原来的A-E是INF无穷大，A-C是3，C-E是4，3+4=7，很明显，7更小，所以我们把INF替换为7  
![在这里插入图片描述][0af5b9b9c2e24f6fb563e2ec241fa1b8.png]  
然后我们看F，原来的A-F是INF无穷大，现在A-C是3，C-F也是INF无穷大，所以我们不管，不用更新了。  
![在这里插入图片描述][c7a205da66484f47a4ddefd04a2492c3.png]  
**这一步就是辅助数组记录起始节点到所有节点的权值的初始化，然后第一次在U集合找出A到哪个节点的权值最小，然后把C移到S集合中，更新了一下辅助数组。**  
然后再接着就是重复刚才的步骤了，从U集合取出当前权值最小的节点，B=5是最小的，然后把B从U集合拿到S集合。  
![在这里插入图片描述][4d292dc046fc49029e550a60a816fba1.png]  
当前辅助数组记录的是A到其他所有节点或者A-C到其他所有节点的当前的最小路径权值  
**然后现在我们要更新一下辅助数组。**  
因为A-C-B到其他的节点的花费可能更小  
我们看D  
现在A-B是5，B-D是5,5+5=10，10小于D现有的6，就不更新了。  
然后我们看E，A-C-B是5，B-E是INF无穷大，不更新了  
然后我们看F，B-F也是INF无穷大，不更新了  
现在就处理完了  
![在这里插入图片描述][d1720a64f81d4afb9e4742b5615ca80f.png]  
**现在D是U集合中权值最小的，把D从U集合移动到S集合中。然后更新一下辅助数组。**  
现在U集合中就剩下E和F了  
我看E，A-D是6，D-E是2,6+2=8，8大于E现有的7，就不更新了。  
然后我们看F，A-D是6，D-F是3,6+3=9，9小于无穷大，更新一下。  
![在这里插入图片描述][50e1af54ea4c4c8b9cb3ca8a50ffc34c.png]  
处理完成。  
然后从U集合找出权值最小的，是E，我们把E从U集合移动到S集合中。  
现在U集合就剩下F了  
我们还要更新一下辅助数组  
A-E是7，我们看F，E-F是5  
7+5=12,12大于F现有的9，不更新  
现在处理完了  
**然后U集合就剩下一个F了，把F从U集合移动到S集合中，OK了**  
![在这里插入图片描述][0f97b75159a94136a3d6e3f7a03fefc0.png]  
现在A到其他所有节点的最短路径的权值已经计算好了。  
但是最短路径信息还没有记录。  
路径记录，记录每一个节点的前驱节点。  
**时间复杂度是O(n^2)**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]

## Dijkstra迪杰斯特拉算法代码实现 ##

package com.fixbug;
    
    import java.util.Arrays;
    
    /**
     * 描述: 迪杰斯特拉算法实现
     *
     * @Author shilei
     * @Date 2019/10/24
     */
    public class Dijkstra {
        
    
        /**
         * 实现一个基于邻接矩阵的带权图最短路径
         * @param start
         * @param end
         */
        public void shortestPath(int start, int end){
        
            //顶点的个数
            final int N = 6;
            //表示节点之间无法到达
            final int INF = 100;
            //定义邻接矩阵------二维数组 
            int[][] graph = new int[][]{
        
                    {
        INF, 6, 3, INF, INF, INF},
                    {
        6, INF, 2, 5, INF, INF},
                    {
        3, 2, INF, 3, 4, INF},
                    {
        INF, 5, 3, INF, 2, 3},
                    {
        INF, INF, 4, 2, INF, 5},
                    {
        INF, INF, INF, 3, 5, INF}
            };//初始化A到其他所有节点的路径权值 
    
            //辅助数组，存储start到其它节点的权值
            int[] cost = new int[N];
            //用来表示节点是否已经计算好最短路径，用来区分S集合和U集合
            boolean[] use = new boolean[N];
            //用来记录节点的前驱节点
            int[] path = new int[N];
    
            //初始化操作
            use[start] = true;//把start节点放入S集合当中
            for (int i = 0; i < N; i++) {
        
                cost[i] = graph[start][i];//初始化辅助数组 
                //更新path数组
                if(cost[i] < INF){
        
                    path[i] = start;//当前节点的前驱是start 
                }
            }
    
            //迪杰斯特拉算法的时间复杂度是O(n^2)
            //开始迪杰斯特拉算法，计算start节点到U集合所有节点的最短路径
            for(int i=1; i < N; ++i){
        
    
                //从U集合当中，找权值最小的节点
                int k = -1;
                int min = INF;
                for (int j = 0; j < N; j++) {
        
                    if(!use[j] && cost[j] < min){
        
                        min = cost[j];
                        k = j;
                    }
                }
    
                //U集合中剩下的顶点都是无法到达的
                if(k == -1){
        
                    break;
                }
    
                //把k节点从U集合放入S集合当中
                use[k] = true;
    
                //更新权值数组 min是start节点到k节点的最短路径
                for (int j = 0; j < N; j++) {
        
                    if(!use[j] && min + graph[k][j] < cost[j]){
        //graph[k][j] 从K到j min是start到K 
                        cost[j] = min + graph[k][j];
                        //这里表示从start走到k，从k再到j，其权值更小，路径更短
                        path[j] = k; 
                    }
                }
            }
    
            System.out.println("最短路径是:" + cost[end]);
            //打印从start是怎么走到end的
            char[] datas = new char[]{
        'A', 'B', 'C', 'D', 'E', 'F'};
            System.out.print(datas[end] + " <- ");
            for(;;){
        
                end = path[end];
                System.out.print(datas[end] + " <- ");
                if(end == start){
        
                    break;
                }
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
        
            Dijkstra dkstra = new Dijkstra();
            dkstra.shortestPath(0, 5);
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/51b4938fe8e144b78bc5a007e55bbebe.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/5425f8d9bca7458c97fc7aad19ba69be.png
[c109f3e243af4415a1e7d26814142bac.png]: /images/20220828/7b7f4c04bdbd455dab9f02a7afb81f91.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/707d47014411470fa0cb70defe5a0f2c.png
[5dd53552f9884d15948de4090869ac02.png]: /images/20220828/d617fbc0da894b53827e60c638039d11.png
[7c5497984a0641d197139d79309767e8.png]: /images/20220828/27e168261f894383bf822d6c935d0f63.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/f3f2fa968b4347109f7c6e55a47f612d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/60190c2a33b54441abad4c5ba64a6fa8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/4286fb0e4d614889a409134af23f9051.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/31860e6df7274a179b75abddf54d8fdd.png
[a204476d682747f6bbda250b9dfa8117.png]: /images/20220828/5b1d1e745b444c2889f3d2bb27079e20.png
[61e2398ded36405294e061b83fecf4f8.png]: /images/20220828/42ff98ef27e742ffb8215292a3a28024.png
[0af5b9b9c2e24f6fb563e2ec241fa1b8.png]: /images/20220828/6747f89649b54590814dbf4a96981b74.png
[c7a205da66484f47a4ddefd04a2492c3.png]: /images/20220828/84c5ec0514bb4abfb104304fa264424f.png
[4d292dc046fc49029e550a60a816fba1.png]: /images/20220828/01f4429d3f7149ca9eb23b3c1e8bc26a.png
[d1720a64f81d4afb9e4742b5615ca80f.png]: /images/20220828/419200ec7a4f43d98ff89811fcb1ece7.png
[50e1af54ea4c4c8b9cb3ca8a50ffc34c.png]: /images/20220828/1f7a6f64ff604a7f86ff04231d5d7e03.png
[0f97b75159a94136a3d6e3f7a03fefc0.png]: /images/20220828/5b9c8f524e0946d5ba19c42c035d8345.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/697e9d9a9c21495386ba3857d7cac2a2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/dfbaadef70e64bdfad831c3d93d6469e.png