卡码网：47.参加科学大会

本题思路：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。

最短路算法中的 dijkstra 算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

迪杰斯特拉算法：

• dijkstra 算法可以同时求 起点到所有节点的最短路径
• 权值不能为负数

迪杰斯特拉算法三部曲：

第一步：找到距离源点最近的且未被访问过的节点

第二步：将该节点标记为已访问（visited数组标记）

第三步：更新未访问过的点距离源点的最小距离（即更新minDist数组）

dijikstra算法与prim算法很相似

在迪杰斯特拉算法中minDist数组用来记录每一个节点距离源点的最小距离

最开始一定要记得将minDist[1] = 0，因为我们就是要求的从节点1到其它所有节点的距离，节点1就是源点。并且此时所有节点都是未被访问的状态。

完整代码如下：

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //minDist 数组 表示 每个节点到源点的最短距离
        int[] minDist = new int[n + 1];
        for(int i = 0; i < minDist.length; i++){
            minDist[i] = 501;
        }
        //邻接矩阵
        int[][] grid = new int[n + 1][n + 1];
        //初始化
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                grid[i][j] = 501;
            }
        }
        //构建图 grid
        for(int i = 0; i < m; i++){
            int s = scanner.nextInt();
            int e = scanner.nextInt();
            int v = scanner.nextInt();
            grid[s][e] = v;
        }
        //迪杰斯特拉算法
        //用来标记是否节点访问过
        boolean[] visited = new boolean[n + 1];
        //本题要求节点1为源点
        minDist[1] = 0;
        //遍历所有节点
        for(int i = 1; i <= n; i++){
            int cur = 1;
            int minVal = 501;
            //第一步：选距离源点最近的节点
            for(int j = 1; j <= n; j++){
                if(!visited[j] && minDist[j] < minVal){//没有访问过的节点
                    minVal = minDist[j];
                    cur = j;
                }
            }
            //第二步：将该节点标记为已访问
            visited[cur] = true;
            //第三步：更新所有其它未访问过的节点到源点的最小距离
            for(int j = 1; j <= n; j++){
                if(!visited[j] && grid[cur][j] != 501 && minDist[cur] + grid[cur][j] < minDist[j]){
                    minDist[j] = minDist[cur] + grid[cur][j];
                }
            }
        }
        //输出结果
        if(minDist[n] == 501){
            System.out.print(-1);
        }else{
            System.out.print(minDist[n]);
        }  
    }   
}

迪杰斯特拉堆优化版

在朴素版本的迪杰斯特拉算法中，使用的三部曲为：

第一步：找到距离源点最近的且没被访问过的节点

第二步：将该节点标记为已访问过

第三步：更新其它未被访问过的点到源点的距离（即更新minDist数组）

在朴素算法中，这三步都是套在一个 for 循环里的。因为朴素算法面向的是点，需要遍历所有节点。

就像prim算法一样面向节点，也会有像Kruskal算法面向边的。

迪杰斯特拉堆优化版就是从边的角度出发：在处理第一步（选源点到哪个节点最近且没被访问过）的时候，就可以不用去遍历所有节点了，而是直接把 边 加入到小顶堆（利用堆来自动排序），那么每次我们从堆顶里取出的边自然是距离源点最近的节点所在的边。

这样我们就不需要两层for循环来寻找最近的节点了。

至此，堆优化版思想已建立。

对于有向图，如何利用邻接表来表述图grid

可以建立一个Edge类，设置两个字段，一个表示邻接节点to，一个表示边的权重val

List<LinkedList<Edge>> grid = new ArrayList<>(n + 1);
class Edge{
    int to;
    int val;
    Edge(int to, int val){
      this.to = to;
      this.val = val;
    }  
} 

堆优化细节：

思路依然是迪杰斯特拉三部曲：

只不过之前是 通过遍历节点来遍历边，通过两层for循环来寻找距离源点最近节点。这次我们直接遍历边，且通过堆来对边排序，达到直接选择距离源点最近节点。

在一步中，我们要选择距离源点最近的节点（即该边的权值最小），所以我们需要一个小顶堆来帮我们对边的权值进行排序，每次从小顶堆堆顶取出元素就是权值最小的边。

使用优先级队列构造自定义Cmparator进行排序。

Pair<Integer, Integer>的第一个Integer表示节点，第二个Integer表示该节点到源点的权值，因为要通过权值在小顶堆中进行排序。

class Pair<U, V> {
    public final U first;
    public final V second;
    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}
//优先级队列中存入 Pair<节点，源点到该节点的权值>
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(
    new Comparator<Pair<Integer, Integer>>(){
    @Override
    public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs){
        return lhs.second - rhs.second;
    }
});

有了小顶堆自动对边的权值进行排序，我们只需要直接从堆里取出堆顶元素，就可以取到离源点最近的节点了。

//minDist数组
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;  // 起始点到自身的距离为 0
// 初始化队列，源点到源点的距离为0，所以初始为0
        pq.add(new Pair<>(start, 0));

所以从上述分析可以得到：三部曲中的第一步，不用for循环去遍历，直接取堆顶元素

Pari<Integer, Integer> cur = pq.poll();
if (visited[cur.first]) continue;

第二步，将该节点进行标记为已访问

visited[cur.first] = true;

第三步，更新非访问节点到源点的距离（不同于邻接矩阵遍历所有节点，这里使用邻接表，只需要遍历该节点的所有边即可，所有的边为grid[cur.first]）

for(Edge edge : grid.get(cur.first)){
    if(!visited[edge.to] &&  minDist[cur.first] + edge.val < minDist[edge.to]){
        minDist[edge.to] = minDist[cur.first] + edge.val;
        pq.add(new Pair<Integer, Integer>(edge.to, minDist[edge.to]));
    }
}

最后输出minDist[n]即可。

完整代码：

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //构建图，采用邻接表实现
        List<LinkedList<Edge>> grid = new ArrayList<>(n + 1);
        for(int i = 0; i <= n; i++){
            grid.add(new LinkedList<>());
        }
        //minDist数组
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;  // 起始点到自身的距离为 0
        for(int i = 0; i < m; i++){
            int s = scanner.nextInt();
            int e = scanner.nextInt();
            int v = scanner.nextInt();
            grid.get(s).add(new Edge(e, v));
        }
        //标记数组
        boolean[] visited = new boolean[n + 1];
        //优先级队列实现小顶堆
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>(){
            @Override
            public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs){
                return lhs.second - rhs.second;
            }
        });
        // 初始化队列，源点到源点的距离为0，所以初始为0
        pq.add(new Pair<>(1, 0));
        while(!pq.isEmpty()){
            //第一步：
            Pair<Integer, Integer> cur = pq.poll();
            if (visited[cur.first]) continue;
            //第二步:
            visited[cur.first] = true;
            //第三步：
            for(Edge edge : grid.get(cur.first)){
                if(!visited[edge.to] &&  minDist[cur.first] + edge.val < minDist[edge.to]){
                    minDist[edge.to] = minDist[cur.first] + edge.val;
                    pq.add(new Pair<Integer, Integer>(edge.to, minDist[edge.to]));
                }
            }
        }
    
        if(minDist[n] == Integer.MAX_VALUE){
            System.out.print(-1);
        }else{
            System.out.print(minDist[n]);
        }
    }   
}

class Edge{
    int to;
    int val;
    Edge(int to, int val){
        this.to = to;
        this.val = val;
    }
    
}

class Pair<U, V>{
    public final U first;
    public final V second;
    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}

至此，迪杰斯特拉两种算法（邻接矩阵 和 邻接表）的实现思想已结束。