求节点间最短路径的Dijastra算法

• 思路概述

  给定一个权值非负的有向连通图， 求某个特定原点(假定节点编号为0)到终点的最短路径权值之和。
  
  Dijastra算法采用贪心思想， 每次选取最短距离可到达的点确定对应路径权值之和， 并用以更新其它邻接点的可到达最短距离直至确定终点或者所有节点的最短路径值。

• 具体步骤

  每次选取可到达的最短距离节点有两种常见方式： 暴力查找最小值或者基于小根堆实现， 这里介绍基于堆的具体步骤

  1. 定义distance数组记录当前可到达每个节点已知的最短距离， 初始只能确定distance[0]=0， 其它节点距离为无穷大； 定义visited数组标记节点是否从堆中弹出过；
  2. 小根堆中维护int[2]数组, arr[0]表示节点编号, arr[1]表示到达该节点时的距离， 初始值将原点对应的[0, 0]加入堆；
  3. 从堆顶取出上一轮维护的所有可到达节点中距离最短的值， 如果该节点没有从堆中弹出过， 说明当前弹出的距离就是该节点的最短路径距离； 如果弹出过就忽略这组继续弹出下一组数据处理；
  4. 遍历当前节点其它边， 如果当前节点最短距离加上边的权值小于边另一端点v已知的最短距离且节点v未从堆中弹出过， 就更新distance[v]的值并将[v, distance[v]]加入堆中用于更新下一轮最短距离的节点信息；
  5. 重复3~4步骤直至目标节点或者所有节点的最短距离都已确定， 即堆中元素全部弹出。

• 数据示例

  用[u, v, distance]表示的图: [[0,6,7], [0,1,2], [1,2,3], [1,3,3], [6,3,3], [3,5,1], [6,5,1], [2,5,3], [0,4,5], [4,6,2]]
  
  PS: 下表中堆中数据按升序展示而不是按底层数据顺序。

  堆顶弹出的元素	堆中元素	更新后的distance数组	更新后的堆	visited数组
  [0, 0]	--	[0, 2, ∞, ∞, 5, ∞, 7]	[1, 2] [4, 5] [6, 7]	[1, 0, 0, 0, 0, 0, 0]
  [1, 2]	[4, 5] [6, 7]	[0, 2, 5, 5, 5, ∞, 7]	[4, 5] [2, 5] [3, 5] [6, 7]	[1, 1, 0, 0, 0, 0, 0]
  [4, 5]	[2, 5] [3, 5] [6, 7]	[0, 2, 5, 5, 5, ∞, 7]	[2, 5] [3, 5] [6, 7]	[1, 1, 0, 0, 1, 0, 0]
  [2, 5]	[3, 5] [6, 7]	[0, 2, 5, 5, 5, 8, 7]	[3, 5] [6, 7] [5, 8]	[1, 1, 1, 0, 1, 0, 0]
  [3, 5]	[6, 7] [5, 8]	[0, 2, 5, 5, 5, 6, 7]	[5, 6] [6, 7] [5, 8]	[1, 1, 1, 1, 1, 0, 0]
  [5, 6]	[6, 7] [5, 8]	[0, 2, 5, 5, 5, 6, 7]	[6, 7] [5, 8]	[1, 1, 1, 1, 1, 1, 0]
  [6, 7]	[5, 8]	[0, 2, 5, 5, 5, 6, 7]	[5, 8]	[1, 1, 1, 1, 1, 1, 1]
  [5, 8]	--	已弹出过，忽略	--	[1, 1, 1, 1, 1, 1, 1]

• 代码示例

    /**
    * n: 节点总数
    * edges: 以[u, v, distance]表示的双向图数据
    */
    public void process(int n, int[][] edges) {
        int[] distance = new int[n];
        
        boolean[] visited = new boolean[n];
        List<int[]> graph = new List[n];// 邻接表
        for (int i = 0; i < n; i++) {
            distance[i] = Integer.MAX_VALUE;
            graph[i] = new ArrayList<>();
        }
        distance[0] = 0;
        for (int[] edge : edges) {
            graph[edge[0]].add(new int[]{edge[1], edge[2]});
            graph[edge[1]].add(new int[]{edge[0], edge[2]});
        }
  
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[1]));
        heap.add(new int[]{0, 0});
        while (heap.size() > 0) {
            int[] arr = heap.poll();
            int u = arr[0], d = arr[1];
            if (visited[u]) {
                continue;
            }
            visited[u] = true;
            for (int[] edge : graph[u]) {
                int v = edge[0];
                if (!visited[v] && distance[v] > d + edge[1]) {
                    distance[v] = d + edge[1];
                    heap.add(new int[]{v, distance[v]})
                }
            }
        }
    }