本文共 8871 字，大约阅读时间需要 29 分钟。

前言

选自

题目描述

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。

如果没有这样的路线，则输出 -1。

本题是非常典型的图论问题，可以使用的算法有深度优先遍历（回溯算法）、Dijkstra 算法、Bellman-Ford 算法。

DFS（回溯算法）

概念

维基百科中关于回溯算法的介绍是：

回溯算法（backtracking）是暴力搜索算法的一种。

这句话向我们揭示了回溯算法的用途：搜索

因此回溯算法也被称为回溯搜索算法。与“二分查找”、“线性查找”等“查找问题”不同的是，“搜索问题”完成一件事情有可能多种方法，而每一种方法又有多个步骤，回溯算法就是在不断尝试，以得到待求问题的全部的解。

回溯法与深度优先遍历的异同

• 相同点

  回溯法在实现上也是遵循深度优先的，即一步一步往前探索，而不像广度优先那样，由近及远一片一片地扫。

• 不同点

  • 1. 访问序

    深度优先遍历：
    目的是“遍历”，本质是无序的。也就是说访问次序不重要，重要的是都被访问过了。
    深度优先只需要把从边界起始的’O’全部访问到即可。因此在实现上，只需要对于每个位置记录是否被visited就足够了。
    回溯法：
    目的是“求解过程”，本质是有序的。也就是说必须每一步都是要求的次序。
    因此在实现上，不能使用visited记录，因为同样的内容不同的序访问就会造成不同的结果，而不是仅仅“是否被访问过”这么简单。
    要使用访问状态来记录，也就是对于每个点记录已经访问过的邻居方向，回溯之后从新的未访问过的方向去访问邻居。
    至于这点点之前有没有被访问过并不重要，重要的是没有以当前的序进行访问。

  • 2. 访问次数

    深度优先遍历：
    已经访问过的节点不再访问，所有点仅访问一次。
    回溯法：
    已经访问过的点可能再次访问，也可能存在没有被访问过的点。

剪枝操作

由于回溯算法的时间复杂度很高，因此，在遍历的时候，如果能够提前知道这一条分支不能搜索到满意的结果，这一分支就可以跳过，这一步操作就是在一棵树上剪去一个枝叶，被人们很形象地称之为剪枝。

回溯算法会大量应用“剪枝”技巧达到以加快搜索速度。这里有几点提示：

1、有时，需要做一些预处理工作（例如排序）才能达到剪枝的目的。虽然预处理工作虽然也消耗时间，但和剪枝能够节约的时间相比是微不足道的。因此，能预处理的话，就尽量预处理；

2、正是因为回溯问题本身时间复杂度就很高，所以能用空间换时间就尽量使用空间。

例题解答

对于该题使用回溯算法，访问每一个有航班的城市，访问经过该城市的路线后，即递归结束，或修改visited，因为可能也有其他路线要经过该点

代码：

class Solution {       int[][] graph;    boolean[] visited;    int res = Integer.MAX_VALUE;    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {           // 初始化图        graph = new int[n][n];        visited = new boolean[n];        // 将航班信息存储图中        for (int[] flight : flights)            graph[flight[0]][flight[1]] = flight[2];                // k+1包含src 后最大经过的城市数        dfs(src, dst, K+1, 0);        if (res == Integer.MAX_VALUE)            return -1;        return res;    }    public void dfs(int src, int dst, int k, int cost) {           // 到达终点直接返回        if (src == dst) {               res = cost;            return;        }                // 如果达到最大途径数，直接返回        if (k == 0)            return;                // 遍历图,找到与src相连的点，即有航班        for (int i = 0; i < graph[src].length; i++) {               // 如果 sec 与 i有航班,并且 i没有访问过            if (graph[src][i] > 0) {                   // 如果访问过就直接跳过                if (visited[i])                    continue;                                // 剪枝操作：跳过可能产生较高费用的路径，从而选出最少价格                if (cost + graph[src][i] > res)                    continue;                                visited[i] = true;                dfs(i, dst, k-1, cost + graph[src][i]);                // 最后递归完回溯                visited[i] = false;              }        }    }}

Dijkstra 算法

概念

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

算法描述：

matrix[i][j]：代表i与j之间的权值，INF代表没有关联 visited[i]：代表起点到 i 顶点的最短距离已经获得 prev[i]：前驱顶点数组，即prev[i]的值是顶点vs到顶点i的最短路径所经历的全部顶点中，位于顶点i之前的那个顶点 dist[i]：长度数组，即 dist[i] 是顶点vs到顶点 i 的最短路径长度

每次都寻找当前未获得的顶点中距离vs最近的点，之后从该点继续延伸，找到vs经过该点后到下一个点距离

代码：

package graph;/** * Dijkstra最短路径：统计图中顶点V到其他顶点的最短路径 * prev--前驱顶点数组，即prev[i]的值是顶点vs到顶点i的最短路径所经历的全部顶点中，位于顶点i之前的那个顶点 * dist--长度数组，即 dist[i] 是顶点vs到顶点i的最短路径长度 */public class Digkstra {       private int mEdgNum;  // 边的数目    private char[] mVex;  // 顶点集合    private int[][] mMatrix;  // 邻接矩阵    private static final int INF = Integer.MAX_VALUE;  //　最大值    public void dijkstra(int vs, int[] prev, int[] dist) {           // flag[i] = true表示顶点vs到顶点i的最短路径已经成功获取        boolean[] flag = new boolean[mVex.length];        // 初始化        for (int i = 0; i < mVex.length; i++) {               flag[i] = false;  // 顶点i的最短路径还未获得            prev[i] = 0;  	// 顶点的前驱顶点为 0            dist[i] = mMatrix[vs][i];  // 顶点i的最短路径为顶点vs到顶点i的权值        }        // 对顶点vs自身进行初始化        flag[vs] = true;        dist[vs] = 0;        // 遍历顶点数－1次，每次找出一个顶点的最短路径        int k = 0;        for (int i = 1; i < mVex.length; i++) {               // 寻找当前最短路径            // 在未获取的顶点中找到距离vs最近的顶点k            int min = INF;            for (int j = 0; j < mVex.length; j++) {                   if (!flag[j] && dist[j] < min) {                       min = dist[j];                    k = j;                }            }            // 标记顶点k为获取最短路径            flag[k] = true;            // 修正当前最短路径和前驱顶点            // 当已经得到顶点k的最短路径之后，更新未获取的顶点的最短路径和前驱顶点            for (int j = 0; j < mVex.length; j++) {                   int tem = (mMatrix[k][j] == INF) ? INF : (min+mMatrix[k][j]);                if (!flag[j] && tem < dist[j]) {                       dist[j] = tem;                    prev[j] = k;                }            }        }    }}

例题解答

该题不需要使用visited数组和dis数组，因为有 K 在约束。

代码：

class Solution {       int[][] graph;    boolean[] visited;    int res = Integer.MAX_VALUE;    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {           // 初始化图        graph = new int[n][n];        visited = new boolean[n];        // 将航班信息存储图中        for (int[] flight : flights)            graph[flight[0]][flight[1]] = flight[2];                // 定义优先队列        PriorityQueue
   
     minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));        // 向集合添加一个记录（起点，费用，站数限制）的数组，K+1 表示可以走过站点的个数        minHeap.offer(new int[]{   src, 0, K+1});        while (!minHeap.isEmpty()) {               int[] front = minHeap.poll();            int v = front[0];            int price = front[1];            int k = front[2];            if (v == dst)                 return price;                        // 如果还可以中转其他战            if (k > 0) {                   for (int i = 0; i < n; i++) {                       // 并且存在一条有向边                    if (graph[v][i] > 0) {                           // 优先队列中存入：有向边指向的顶点 i、从起点 src 到 i 的总路径长度、还有多少站可以中转                        minHeap.offer(new int[]{   i, price+graph[v][i], k-1});                    }                }            }        }        return -1;    }}
   

Bellman-Ford 算法

简介

贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard

Bellman） 和莱斯特·福特创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为Edward F.Moore也为这个算法的发展做出了贡献。

…

它的原理是对图进行 V-1 次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。

来源百度百科

算法

贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。

…

在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。

…

然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；

而贝尔曼-福特算法简单地对所有边进行松弛操作，共 V-1 次，其中是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

最短路径

最短路径：是指连接图中两个顶点的路径中，所有边构成的权值之和最小的路径。

最短路径中不能包含负权回路，因为每次经过负权回路，路径的权值会减少，所以这种情况下不存在最短路径。有些图结构中会存在负权边，用于表达通过某条途径可以降低总消耗

在有向图中，负权边不一定会形成负权回路，所以在一些计算最短路径算法中，负权边也可以计算出最短路径；

在无向图中，负权边就意味着负权回路，所以无向图中不能存在负权边。

…

后续的所有讨论都设定图中不存在负权回路的情况。

摘自简书

松弛函数

对边集合 E 中任意边，以 w(u,v) 表示顶点 u 出发到顶点 v 的边的权值，以 d[v] 表示当前从起点 s 到顶点 v 的路径权值

若存在边 w(u,v)，使得：

d[v] > d[u] + w(u,v)

则更新 d[v] 值：

d[v] = d[u]+w(u,v)

所以松弛函数的作用，就是判断是否经过某个顶点，或者说经过某条边，可以缩短起点到终点的路径权值。

为什么将缩短距离的操作称之为“松弛”，不妨理解为，选择某种方式后，到达目的的总代价降低了。什么名字无关紧要，不必纠结。

松弛函数代码示例

// 修正当前最短路径和前驱顶点// 当已经得到顶点k的最短路径之后，更新未获取的顶点的最短路径和前驱顶点for (int j = 0; j < mVex.length; j++) {       int tem = (mMatrix[k][j] == INF) ? INF : (min+mMatrix[k][j]);    if (!flag[j] && tem < dist[j]) {           dist[j] = tem;        prev[j] = k;    }}

例题解答

注意到题目限制 K 次中转，这件事情特别像「Bellman-Ford 算法」描述中的操作：「我们对图中的每条边执行顶点次数−1次松弛操作，看看多绕一个顶点会不会使得最短路径短」。

…

因此，我们使用 dp[i][j] 表示从顶点 src 到其它顶点 i 经过了 j 次松弛操作（也就是经过了 j 个顶点）以后得到的最短路径。

…

d[i][j]：也可以这样理解：是起点经过k个中转站后到达站 i 的最小费用

import java.util.Arrays;public class Solution {       public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {           int maxPrice = 1_000_000_000;        int[][] dp = new int[n][K + 1];        // 初始化 1：由于找最短路径，因此初始化的时候赋值成为一个不可能的较大的值        for (int i = 0; i < n; i++) {               Arrays.fill(dp[i], maxPrice);        }        // 自己到自己，不管经过几个顶点，最短路径都是 0，初始化dst = src的行        for (int i = 0; i <= K; i++) {               dp[src][i] = 0;        }        // 第 1 轮松弛操作，只需要对从 src 出发的边进行松弛操作        // 利用flights中的信息初始化src可直达的班次        for (int[] flight : flights) {               if (flight[0] == src) {                   dp[flight[1]][0] = flight[2];            }        }        // 第 2 轮到第 K + 1 轮松弛操作，最后一轮松弛操作是为了检测是否可达        // 直达的已经初始化了（即k = 0的情况），现在从k = 1 的开始，即只有一个中转站开始        for (int i = 1; i <= K; i++) {               for (int[] flight : flights) {                   int from = flight[0];                int to = flight[1];                // 每一次松弛操作的结果是互相独立的，因此只有在上一轮（第 i - 1 轮）得到单源最短路径的顶点，才需要执行松弛操作                // 判断src到from(当前班次的起点)经过i-1个城市，是否可以到达                if (dp[from][i - 1] != maxPrice) {                   	// 更新src到to的经过i个城市的最小花费,比较src到from+from到to的班次的花费与src直接到to的最小花费.更新操作                    dp[to][i] = Math.min(dp[from][i - 1] + flight[2], dp[to][i]);                }            }        }        // 如果不可达，返回 -1        if (dp[dst][K] == maxPrice) {               return -1;        }        return dp[dst][K];    }}

感谢

代码来自摘抄，学习而非商业用途，感谢大神！

加油！