最短路算法——迪杰斯特拉（Dijkstra)算法

素颜马尾好姑娘i 2023-07-16 08:57 68阅读 0赞

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

https://blog.csdn.net/goodxin\_ie/article/details/88707966  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1]

1.  初始时从1开始寻找各节点到该节点的距离，路不通设置为maxint，此时把1归为s里面
2.  从1）得到距离1最短的路径对应的结点如上图为2，并把2归到s里面并求各节点（剩下的不在s里面的）到2的距离，如果新的距离更小的话则更新dist\[i\]
3.  从2）得到距离2最短的路径对应的结点如上图为4，并把4归到s里面并求各节点（剩下的不在s里面的）到4的距离，如果新的距离更小的话则更新dist\[i\]
4.  依次类推可以把算有的节点遍历，并且最终的dist\[i\]便是从初始节点1到i的最短路径

## 算法实现 ##

import java.util.HashSet;
    import java.util.Set;
    
    public class Dijkstra { 
        public static void main(String[] args) { 
            int[][] road = { { 0, 1, 6, -1, 7},{ 1, 0, 2, 8, -1},{ 6, 2, 0, 1, 1},{ -1, 8, 1, 0, -1},{ 7, -1, 1, -1, 0}};
            int[] res = new Dijkstra().getShort(road);
            for(int i = 0; i < road[0].length; i++){ 
                System.out.println("节点0到节点" + i + "的最短路为：" + res[i]);
            }
        }
    
        //数组raod中，如果两点不连通，则值为-1
        public int[] getShort(int[][] road){ 
    
            //res用于记录最短路，初始化res
            int[] res = new int[road.length];
            for(int i = 0; i < road[0].length; i++){ 
                res[i] = road[0][i];
            }
    
            //用于记录哪些节点是已经遍历过了
            Set<Integer> set = new HashSet();
            set.add(0);
    
            //index表示现在是遍历哪个节点
            int index = 0;
            while(set.size() < road.length){ 
                //通过选出res中最小的那个，来确定遍历的节点
                int min = Integer.MAX_VALUE;
                for(int i = 1; i < road[0].length; i++){ 
                    if(!set.contains(i) && res[i] >= 0 && res[i] < min){ 
                        min = res[i];
                        index = i;
                    }
                }
                //System.out.println(index);
    
                //遍历节点index，如果它到某个节点的距离road[index][i]，加上起点到它的最短距离res[index]，要小于res[i]，就替换res[i]
                for(int i = 0; i < road[index].length; i++){ 
                    if(road[index][i] >= 0){ 
                        if(res[i] < 0 || road[index][i] + res[index] < res[i]){ 
                            res[i] = road[index][i] + res[index];
                        }
                    }
                }
                set.add(index);
            }
            //System.out.println(set);
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70]: /images/20230528/f272332c7afe481ea7a4011d98dd9822.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1]: /images/20230528/4d3e239e1be84329819f78d6ca5ddf07.png