Dijkstra算法

先熟悉图的基本概念和图的基本遍历算法（DFS/BFS），再来看这些算法会更好理解呦！

概述

Dijkstra算法是一种用于解决 单源最短路径问题 的算法，由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出。

该算法主要用于在加权图（有向无向均可）中找到从一个起点到其他所有顶点的最短路径，所有边的权重应该 都是非负的。

主要步骤

已知条件：图结构 neighbors（可以获取每个节点的邻接点和权重）和起点节点编号 start；
初始化：
1. 定义一个数组 dist，dist[i] 表示起点到节点 i 的最短路径（这里路径定义为起点到节点 i 经过的权重和）；
  1. 初始 dist[i] 都为极大值，表示未知状态；
  2. dist[start] = 0，起点到起点本身距离为 0；
2. 定义一个数组 visited 表示每个节点是否处理过，初始都为 false表示未处理；
选择当前未处理节点中距离最短的：我们每次从未处理的节点中选择出距离最短的节点 minNode，将它标记为已处理；
更新邻接点的距离：基于距离最短的节点 minNode，更新它的邻接点的距离；
重复 3 和 4，直到没有 minNode，即 所有节点都被处理或者有节点不可达；

原理概述

Dijkstra 算法的核心思想是贪心法，通过逐步扩展当前已知的最短路径，直到找到从起点到所有其他顶点的最短路径。

所有边的权重都是非负的是算法正确运行的前提。

也就是贪心的策略：我们每次都从当前最短距离去更新其他未处理节点，如果 未处理节点当前得到的距离并不是最终的结果，它是不可能是未处理节点中距离最短的节点。

代码示例

算法的步骤2和步骤4和一般图论算法是类似的（如 DFS 或 BFS），关键在于找到当前未处理节点中距离最短的节点。

图结构通常会以一个列表的形式给出，如 edges。列表中每个元素存放一组节点的连接关系，即 edge[i] = [node1, node2]（如果是有权图，则有权重信息；如果是有向图的话，一般是 node1 -> node2，代码以有向图示例）

我们通常需要将这个“边信息”列表转成一个“节点信息”列表 graph，graph[i]也是一个列表，存储节点 i 的所有邻节点。

函数参数：

edges：图中的所有边信息，形式如 [node1, node2]；如果是带权重的，则形式如 [node1, node2, weight]；有向图和无向图的区别仅在于构建图结构，不影响 Dijsktra 算法；
n：节点总数；节点编号为 [0,n-1]，定义的数组长度为 n；节点编号为 [1,n]，定义的数组长度为 n+1；【核心要保证每个节点编号作为数组索引都合法】
k：搜索起点；

朴素Dijsktra

最直接的就是枚举 dist[i]，找到其中未处理的节点（visited[i]=false）的最小值；

这种策略每个节点都会当一次未处理节点中距离最短的节点（相当于不断把距离短的节点淘汰），即大循环执行 n 次；

而找一个距离最短的节点需要 O(n) 的复杂度，即小循环执行 n次，因此总的时间复杂度为 O(n^2)；

Java

Python

C++

class Solution{
    public int[] dijkstra(int[][] edges, int n, int k){
        // 构建图
        List<int[]>[] neighbors = new ArrayList[n];             // 邻接表，neighbors[i]存储节点i的所有邻节点和对应权重
        for(int i = 0; i < n; i++){
            neighbors[i] = new ArrayList<>();                   // 初始化每个节点的邻接表neighbors[i]
        }
        for(int[] e: edges){                                    // 枚举每一条边edge的信息
            neighbors[e[0]].add(new int[]{e[1], e[2]});         // 根据给定的边添加数据
        }
        // Dijkstra算法
        int[] dist = new int[n];                // dist[i]存储源点k到节点i的最短距离，初始都为极大值
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[n];     // visited[i]存储节点i是否被访问过，初始都为false
        dist[k] = 0;                            // 源点到源点的距离为0
        while(true){
            // 找到 当前未处理节点中距离源点k最近的节点
            int minNode = -1;                       // minNode存储节点编号
            for (int i = 0; i < n; i++) {
                if (!visited[i] && (minNode == -1 || dist[i] < dist[minNode])) {
                    minNode = i;                    // 更新当前距离源点k最近的未处理节点
                }
            }
            // 最短距离节点未更新，即所有节点都处理过了
            // 未处理节点的最小距离就是极大值，说明剩下的节点都不可达
            if(minNode == -1 || dist[minNode] == Integer.MAX_VALUE)break;
            visited[minNode] = true;                                  // 标记最短路径的未处理节点已处理
            for(int[] neighborInfo: neighbors[minNode]){              // 更新最短距离节点的邻接点距离
                int v = neighborInfo[0], w = neighborInfo[1];         // 邻节点v和minNode->v的权重
                dist[v] = Math.min(dist[v], dist[minNode] + w);       // 更新邻接点v的最短距离
            }
        }
        return dist;
    }
}

堆优化 Dijsktra

我们也可以将寻找最小值的过程交给小顶堆来处理。我们每次更新邻接点距离的时候，将邻接点和距离加入小顶堆从而得到下一个最短距离的节点。

这种策略加入到小顶堆的节点数目取决于边的数目，也就是节点会重复添加。即堆中的元素个数可以认为为边的个数 m。

那么取堆顶元素最坏情况就可能取 m 次，小顶堆每次排序需要 logm复杂度，此总的时间复杂度为 O(mlogm)；

Java

Python

C++

class Solution{
    public int[] dijkstra(int[][] edges, int n, int k){
        // 构建图
        List<int[]>[] neighbors = new ArrayList[n];             // 邻接表，neighbors[i]存储节点i的所有邻节点和对应权重
        for(int i = 0; i < n; i++){
            neighbors[i] = new ArrayList<>();                   // 初始化每个节点的邻接表neighbors[i]
        }
        for(int[] e: edges){                                    // 枚举每一条边edge的信息
            neighbors[e[0]].add(new int[]{e[1], e[2]});         // 根据给定的边添加数据
        }
        // Dijkstra算法
        int[] dist = new int[n];                // dist[i]存储源点k到节点i的最短距离，初始都为极大值
        Arrays.fill(dist, Integer.MAX_VALUE);
        Queue<int[]> pq = new PriorityQueue<>(
                Comparator.comparingInt(p -> p[0])
        );                                      // 小顶堆，每个元素：(起点k到节点i的最短距离，节点i)
        dist[k] = 0;                            // 源点到源点的距离为0
        pq.offer(new int[]{0, k});              // 将源点k加入小顶堆
        while(!pq.isEmpty()){
            // 找到 当前未处理节点中距离源点k最近的节点
            int[] nodeInfo = pq.poll();
            int minNode = nodeInfo[1], minDist = nodeInfo[0];
            // 该节点已处理，跳过
            if(minDist > dist[minNode])continue;
            for(int[] neighborInfo: neighbors[minNode]){                        // 更新最短距离节点的邻接点距离
                int v = neighborInfo[0], ds= dist[minNode] + neighborInfo[1];   // 邻节点v和新的距离ds
                if(ds < dist[v]){
                    dist[v] = ds;                   // 新的距离更短，就更新节点v的最短路径
                    pq.offer(new int[]{ds, v});     // 路径一旦更新就要入队，从而得到正确的最短路径节点
                }
            }
        }
        return dist;
    }
}

小结

如果边的个数远小于节点个数的平方（称作稀疏图），可以使用堆优化的 Dijsktra；

否则（称作 稠密图），可以使用朴素的 Dijsktra；