图论之最短路问题详细介绍和例题练习_根据图的变化情况选择合适的方法跑最短路

最短路

图的最短路算法有很多，以下常用的三个算法

• 单源最短路
  • 不带负权边：Dijkstra
  • 带负权边：Bellman-Ford、SPFA
• 多源最短路
  • Floyd

单源最短路

Dijkstra

• 算法思想：每次找到离起始点最近的一个点，以该点为中心，更新起始点到其他点的最短路径。该算法无法判断是否存在负权环路，如果存在，算法将失效。
• 算法本质是贪心+广度搜索
• 朴素写法，时间复杂度O(V²+E)，可以认为是O(V²)，这个一般不怎么用
• 堆优化（小根堆），时间复杂度O(VlogV+E)
• Dijkstra 算法更适合稠密图（边多的图）
• 无论图有没有环，Dijkstra 算法都是可以用的，它只是不能处理负权边，因为它本质上是贪心策略，每个点选择之后就不再更新，如果碰到了负边的存在就会破坏这个贪心的策略就无法处理了。
• 一般堆优化+邻接矩阵用起来很好用

算法模板

   // 朴素写法

    private int s;    // 起始点
    private int[] dis; // 存储起始点到每个点的最短距离
    private boolean[] visited;  

    public Dijkstra(WeightedGraph G, int s) throws Exception {
        dis = new int[G.V()];
        visited = new boolean[G.V()];
        Arrays.fill(dis,Integer.MAX_VALUE);
        dis[0] = 0;

        while (true){
            int curdis = Integer.MAX_VALUE,cur = -1;

            for (int v = 0; v < G.V();v++){
                if (!visited[v] && dis[v] < curdis){
                    curdis = dis[v];
                    cur = v;
                }
            }

            if (cur == -1) break;

            visited[cur] = true;

            for (int w : G.adj(cur)){
                if (!visited[w]){
                    // G.getWeight(cur,w) 代表cur点到w点的距离
                    dis[w] = Math.min(dis[cur] + G.getWeight(cur,w) , dis[w]);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// 堆优化写法

    public Dijkstra2(WeightedGraph G, int s) throws Exception {
        dis = new int[G.V()];
        visited = new boolean[G.V()];
        Arrays.fill(dis,Integer.MAX_VALUE);

        pre = new int[G.V()];
        Arrays.fill(pre,-1);

        dis[s] = 0;
        pre[s] = s;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(s,0));

        while (!pq.isEmpty()){

            int cur = pq.remove().v;
            if (visited[cur]) continue;

            visited[cur] = true;

            for (int w : G.adj(cur)){
                if (!visited[w]){
                    if (dis[cur] + G.getWeight(cur,w) < dis[w]){
                        dis[w] = dis[cur] + G.getWeight(cur,w);
                        pq.add(new Node(w,dis[w]));
                        pre[w] = cur;
                    }
                }
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Bellman_ford

• 算法思想：假设dis[i]为起始点到节点的最短路径，显然这条路径上最多包含n - 1条边，那么我们可以通过 n - 1 次循环，每次循环松弛所有边，根据路径松弛定理，最终我们可以得到正确的答案。由于进行了全面的松弛，最后得到的结果根据三角形定则，一定有 dis[v] < dis[u] + w(假设有边u->v = w)，否则即存在负边回路。
• 时间复杂度：O(NE)。最坏情况下，E = n²，此时的复杂度是O(n³)级别的。
• 空间复杂度：O(N)。

算法模板

   public BellmanFord(WeightedGraph G, int s) throws Exception {

        dis = new int[G.V()];
        Arrays.fill(dis,Integer.MAX_VALUE);
        dis[s] = 0;

        pre = new int[G.V()];
        Arrays.fill(pre,-1);

        for (int pass = 1; pass < G.V();pass++){

            for (int v = 0; v < G.V(); v++){
                for (int w : G.adj(v)){
                    if (dis[v] != Integer.MAX_VALUE && dis[v] + G.getWeight(v,w) < dis[w]){
                        dis[w] = dis[v] + G.getWeight(v,w);
                        pre[w] = v;
                    }
                }
            }

        }

        for (int v = 0; v < G.V(); v++){
            for (int w : G.adj(v)){
                if (dis[v] != Integer.MAX_VALUE && dis[v] + G.getWeight(v,w) < dis[w]){
                    hasNegativeCycle = true;
                }
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

SPFA

• 算法思想：初始化 dis[k] = 0，而其他值等于一个无穷大的数，该算法类似于BFS，但又不同于BFS，先将k加入队列，对k的邻边进行松弛，如果松弛成功，说明这个邻接点v的dis值改变，那么就有可能通过点v对其邻边进行松弛，所以我们将v点加入队列，如果v已在队列，则我们可以不加入它，最后我们将k出队，重复此操作。可以看出该算法与BFS的一个重大区别在于该算法出队之后可以二次入队。
• 它是 Bellman-Ford的优化， Bellman−Ford 的时间复杂度为 O(VE)，效率太低了，SPFA是 Bellman-Ford的队列优化，但是算法时间效率不稳定，时间复杂度为 O(E)，最好情况下，每个节点只入队一次，就是 BFS，最坏情况下，每一个节点都要入队 V-1次，这时候就退化成 Bellman-Ford了
• SPFA时间复杂度某种情况下略高于 Dijkstra， 适合稀疏图
• SPFA是可以用于带有负权图的，在 SPFA中每一个点松弛过后说明这个点距离更近了，所以有可能通过这个点会再次优化其他点，所以它的策略是将 vis 位置为 false，把这个点入队再判断一次！这就和 Dijkstra 的贪心策略不同了！
• SPFA还有个用处是可以判断图是否存在负环，我们只要用一个 cnt[x] 数组来存放经过这个点的次数，上面提到过，最坏情况下每个节点入队 V-1次，如果 cnt[x]为 V 的个数，那就说明存在负环了。

算法模板

    private int s;
    private int[] dist;
    private boolean[] visit;
    private Queue<Integer> queue;

    public int spfa(WeightedGraph G, int s) throws Exception {

        int n = G.V();
        dist = new int[n];
        visit = new boolean[n];
        Arrays.fill(dist,Integer.MAX_VALUE);
        queue = new LinkedList<>();

        dist[s] = 0;
        queue.add(s);
        visit[s] = true;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            visit[cur] = false;

            for (int w : G.adj(cur)) {
                if (dist[w] > dist[cur] + G.getWeight(cur,w)) {
                    dist[w] = dist[cur] + G.getWeight(cur,w);
                    if (!visit[w]) {
                        queue.add(w);
                        visit[w] = true;
                    }
                }
            }
        }
        return dist[n-1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

多源最短路

Floyd

• 算法思想：该算法通常用以解决所有节点对的最短路径，该算法利用了这样一个有趣的事实：如果从节点 i 到节点 j，如果存在一条更短的路径话，那么一定是从另一个节点 k 中转而来，即有 d[i][j] = min(d[i][j],d[i][k]+d[k][j])，而d[i][k]和d[k][j]可以用一样的思想去构建，可以看出这是一个动态规划的思想。在构建i,j中，我们通过枚举所有的k值来进行操作。同样，该算法无法判断负权回路。
• 本质是动态规划，能解决任意两点间的最短路径，时间复杂度 O(V^3)
• Floyd它是可以判断有没有负权边环的，走 N-1步，如果再走一步，更短了，那么就说明有环。另外 Floyd是不能处理带有负权的最短路的，因为本质是一个动态规划算法，有了负边，最优子结构的性质就不满足了。由此可见，它能够判断是否存在负环，但是不能够处理带有负权的额最短路
• Floyd有个神奇的特性，这个是其他算法没有的， Floyd第 k轮算的结果，是每个源点到每个汇点经过前 k 个点的最短路。

算法模板

    private int[][] dis;
    private boolean hasNegativeCycle;

    public Floyed(WeightedGraph G) throws IllegalAccessException {
        this.G = G;

        dis = new int[G.V()][G.V()];

        for (int i = 0;i < G.V();i++){
            Arrays.fill(dis[i],Integer.MAX_VALUE);
        }

        //  初始化图
        for (int v = 0;v < G.V();v++){
            dis[v][v] = 0;
            for (int w : G.adj(v)){
                dis[v][w] = G.getWeight(v,w);
            }
        }

        for (int t = 0; t < G.V();t++){
            // 最外层的循环相当于是把所有节点遍历一遍，判断可以从v节点 通过 t节点间接达到 w节点的情况
            for (int v = 0; v < G.V();v++){
                for (int w = 0; w < G.V();w++){
                    // 遍历从v节点到w节点可能存在的路径 同时和 从v节点 通过 t节点间接达到 w节点的情况 做比较，得出最短路径的值
                    if (dis[v][t] != Integer.MAX_VALUE && dis[t][w] != Integer.MAX_VALUE &&
                            dis[v][t] + dis[t][w] < dis[v][w]){

                        dis[v][w] = dis[v][t] + dis[t][w];
                    }
                }
            }
        }

        for (int v = 0; v < G.V(); v++){
            if (dis[v][v] < 0) hasNegativeCycle = true;
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

最短路例题

• 743. 网络延迟时间

• 787. K 站中转内最便宜的航班

• 1334. 阈值距离内邻居最少的城市

• 814. 无向图中的最短路径

• Sightseeing Trip

• 孤岛营救问题

• 架设电话线

• 农场派对

• Roadblocks

• 最短路计数

• 新年好

• 最优贸易

• 汽车加油行驶问题

• 道路和航线