单源最短路（优先队列优化的dijkstra算法）：PIPI的飞行路线

文章目录

单源最短路（优先队列优化的dijkstra算法）：PIPI的飞行路线

dijkstra算法

dijkstra算法用于解决不含负权边单源最短路径问题。首先要知道两个点之间的最短路径有以下两种情况：
（1）连接两点的边本身就是最短的。
（2）两点之间通过一些中间节点相连得到最短距离。
dijkstra算法用dis数组保存当前源点s距离其他点的最短距离。初始时，dis数组除了源点离自己的距离dis[s]为0，其他全为INF。dijkstra算法利用了贪心的思想，每次从dis数组中筛出最短距离还未确定且最小的dis[x]，此时源点到顶点x的最短距离就确定了(不可能更小了)，然后从x出发更新其相邻节点的最短距离。dijkstra算法重复上述过程直到所有顶点的最短距离都确定。
朴素的dijkstra算法的时间复杂度为O(n^2)，筛出数组中最短距离需要O(n)，更新相邻结点的最短距离需要O(n)。我们可以用优先队列对筛选最短距离的过程进行优化。
使用优先队列优化的dijkstra算法与使用优先队列的BFS算法如出一辙。同样的，我们用dis数组保存当前源点s距离其他点的最短距离。初始时，dis数组除了源点离自己的距离dis[s]为0，其他全为INF。之后，将源点s压入优先队列，开始BFS过程。对于每次出队的结点u，我们对其连接的下个结点v进行判断，如果dis[v]>dis[u]+(u,v)边权，则更新dis [v] (即令dis[v]=dis[u]+(u,v)边权)，并将v结点入队。重复上述过程直到队列中再无任何结点，最终得到的dis数组即为源点s到各点的最短路径。优先队列将朴素方法中筛选最短距离的过程进行优化，将O(n)优化到了O(logn)

在朴素的dijkstra算法中，我们会使用一个标记数组来表示源点到某结点的最短距离是否已经确定，若确定了，则可以不进行最短路径的更新了。而在优先队列的优化下，可以不使用标记数组了。我们每次向队列中加入结点都会附带源点到该节点暂时得到的最短路径，若我们从队列中取出的头结点中的该路径值比dis[]数组中的距离大，则证明该状态可以被舍弃，已经有更优的从源点走到该节点的路径，我们可以使用该判断过滤掉无用的状态，通过不断更新最短距离，最终dis[]数组也会维持到所有最短距离都确定的状态，因此可以不使用标记数组了。

优先队列版的dijkstra算法模板如下，时间复杂度为O((n+m)*logn)：

    static final int INF = 100000009;
    static Queue<Node> q = new PriorityQueue<>();
    // 邻接表
    static ArrayList<Node>[] adj = new ArrayList[10002];
    // 距离数组dis[]
    static int[] dis = new int[10002];

    static void dijstra(int s) {
        int i, index, dis, indexOther, weight;
        // dis数组初始化
        for (i = 1;i <= n;i++) {
            dis[i] = INF;
        }
        // 源点到自己的距离为0
        dis[s] = 0;
        q.add(new Node(s, 0));
        Node node;
        while (!q.isEmpty()) {
            node = q.poll();
            index = node.index;
            dis = node.distance;
            // 若该节点保存的distance大于dis数组中保存的从s到该节点的最短路径，则直接舍弃该状态
            if (dis > distance[index]) {
                continue;
            }
            for (i = 0;i < adj[index].size();i++) {
                indexOther = adj[index].get(i).index;
                weight = adj[index].get(i).distance;
                // 更新最短路径
                if (distance[indexOther] > dis + weight) {
                    distance[indexOther] = dis + weight;
                    q.add(new Node(indexOther, distance[indexOther]));
                }
            }
        }
    }

    class Node implements Comparable<Node> {
        public int index;
        public int distance;
        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return this.distance - o.distance;
        }
    }

问题：

思路：

此题在单源最短路的基础上增加了一个免费路线情况，麻烦点也在于此，我们可以从所有免费路线中选取一条
所有可选的免费路线并不多，我们会想到枚举所有情况，寻找最短距离，那么如何比较选取一条免费路线比另一条免费路线好呢？若我们选取(u,v)这条免费路线，那么我们从源点s到终点n只有两种情况：

s——>u——>v——>n
s——>v——>u——>n

考虑dijkstra算法最后得到的dis[]数组,我们可以知道s——>u和s——>v的最短距离，而从u——>v和从v——>u的距离为0，最后只剩下从v——>n和u——>n的最短距离，注意到该题中的图为无向图，因此v——>n和n——>v的最短距离是相等的。因此我们再将n设为源点，进行一次dijkstra算法，得到n到其他点的最短距离。这样我们就能比较选择不同免费线路，哪个最短了。若用dis1[]表示源点为s的距离数组，dis2[]表示源点为n的距离数组，则选择(u,v)免费路线，从s到n的最短距离为：
min(dis1[u]+dis2[v],dis1[v]+dis2[u])
枚举所有免费路线的情况，获取使用免费机票时的最短路径，再与不选取免费路线的最短路径比较，较小者即为答案

代码：

import java.util.*;

public class Main {
    static final int INF = 100000009;
    static Queue<Node> q = new PriorityQueue<>();
    static ArrayList<Node>[] adj = new ArrayList[10002];
    static int[] dis1 = new int[10002];
    static int[] disN = new int[10002];
    public static void main(String[] args) {
        int i, n, m, u, v, c, k, ans;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (i = 0;i <= n;i++) {
            dis1[i] = INF;
            disN[i] = INF;
            adj[i] = new ArrayList<>();
        }
        dis1[1] = 0;
        disN[n] = 0;
        for (i = 0;i < m;i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            c = scanner.nextInt();
            adj[u].add(new Node(v, c));
            adj[v].add(new Node(u, c));
        }
        q.add(new Node(1, 0));
        dijstra(dis1);
        q.add(new Node(n, 0));
        dijstra(disN);
        ans = dis1[n];
        k = scanner.nextInt();
        for (i = 0;i < k;i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            ans = Math.min(ans, Math.min(dis1[u] + disN[v], disN[u] + dis1[v]));
        }
        if (ans == INF) {
            System.out.println("No way!");
        } else {
            System.out.println(ans);
        }
    }

    static void dijstra(int[] distance) {
        Node node;
        int i, index, dis, indexOther, weight;
        while (!q.isEmpty()) {
            node = q.poll();
            index = node.index;
            dis = node.distance;
            if (dis > distance[index]) {
                continue;
            }
            for (i = 0;i < adj[index].size();i++) {
                indexOther = adj[index].get(i).index;
                weight = adj[index].get(i).distance;
                if (distance[indexOther] > dis + weight) {
                    distance[indexOther] = dis + weight;
                    q.add(new Node(indexOther, distance[indexOther]));
                }
            }
        }
    }

}

class Node implements Comparable<Node> {
    public int index;
    public int distance;
    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node o) {
        return this.distance - o.distance;
    }
}