算法图算法

带权图最短路径的变种问题

字数统计: 4.4k字   |   阅读时长: 21分
, ,

摘要: 带权图最短路径的变种问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 带权图最短路径算法与实现 中我们以力扣 743 作为模板题，全面梳理了带权图最短路径的各种算法与实现。

本文我们例举一些以带权图最短路径问题为基础的各种变种问题。以算法进行分类，涉及 BFS、dijkstra、bellman ford、floyd 等算法，如下：

在拿到实际问题时，怎样选择算法还是有一些经验的。权均为 1 的话，首选 BFS；没有负权的话，一般用 dijkstra 最好；如果有负权，考虑 bellman ford；多源的问题，考虑 Floyd。

BFS

815. 公交路线

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

  • 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

提示：

1
2
3
4
5
6
1 <= routes.length <= 500.
1 <= routes[i].length <= 1e5
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 1e5
0 <= routes[i][j] < 1e6
0 <= source, target < 1e6

示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。

示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

算法：建图 + BFS

难点在于建图: 将每一条公交路线（而不是每一个车站）看成图中的一个点，如果两条公交路线有交集，那么它们在图中对应的点之间就有一条边。此外，起点站 S 和终点站 T 也分别是图中的一个点，如果一条公交路线包含了 S 或 T，那么也需要和 S 或 T 对应的点连一条边。此时，在这个图上从 S 到 T 的最短路径长度即为答案。

代码 (C++)

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if(S == T) return 0;
        int n_route = routes.size();
        vector<vector<int> > g(n_route, vector<int>()); // 以站点 id 建图
        // routes 中每个线路
        vector<int> starts;
        unordered_set<int> ends;
        for(int i = 0; i < n_route; ++i)
        {
            sort(routes[i].begin(), routes[i].end());
            auto it_start = lower_bound(routes[i].begin(), routes[i].end(), S);
            auto it_end = lower_bound(routes[i].begin(), routes[i].end(), T);
            if(it_start != routes[i].end() && *it_start == S)
                starts.push_back(i);
            if(it_end != routes[i].end() && *it_end  == T)
                ends.insert(i);
        }
        vector<int> intersect(500);
        for(int i = 0; i < n_route - 1; ++i)
            for(int j = i + 1; j < n_route; ++j)
            {
                auto it = set_intersection(routes[i].begin(), routes[i].end(), routes[j].begin(), routes[j].end(), intersect.begin());
                if(it != intersect.begin())
                {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        queue<int> q;
        vector<bool> visited(n_route, false);
        for(int i: starts)
        {
            q.push(i);
            visited[i] = true;
        }
        int result = 1;
        vector<int> level_nodes;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                int cur = q.front();
                q.pop();
                if(ends.find(cur) != ends.end())
                    return result;
                level_nodes.push_back(cur);
            }
            ++result;
            for(int node: level_nodes)
            {
                for(int son: g[node])
                {
                    if(visited[son]) continue;
                    visited[son] = true;
                    q.push(son);
                }
            }
        }
        return -1;
    }
};

864. 获取所有钥匙的最短路径

本题涉及到状态压缩 BFS，题解参考文章 【搜索难题】力扣864-获取所有钥匙的最短路径。

dijkstra

882. 细分图中的可到达结点

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。

图用由边组成的二维数组 edges 表示，其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边，cnti 是将边 细分 后的新节点总数。注意，cnti == 0 表示边不可细分。

要 细分 边 [ui, vi] ，需要将其替换为 (cnti + 1) 条新边，和 cnti 个新节点。新节点为 x1, x2, …, xcnti ，新边为 [ui, x1], [x1, x2], [x2, x3], …, [xcnti-1, xcnti], [xcnti, vi] 。

现在得到一个 新的细分图 ，请你计算从节点 0 出发，可以到达多少个节点？如果节点间距离是 maxMoves 或更少，则视为 可以到达 。

给你原始图和 maxMoves ，返回 新的细分图中从节点 0 出发 可到达的节点数 。

提示：

1
2
3
4
5
6
7
0 <= edges.length <= min(n * (n - 1) / 2, 1e4)
edges[i].length == 3
0 <= ui < vi < n
图中 不存在平行边
0 <= cnti <= 1e4
0 <= maxMoves <= 1e9
1 <= n <= 3000

示例 1：
输入：edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
输出：13
解释：边的细分情况如上图所示。
可以到达的节点已经用黄色标注出来。

示例 2：
输入：edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
输出：23

示例 3：
输入：edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
输出：1
解释：节点 0 与图的其余部分没有连通，所以只有节点 0 可以到达。

算法：dijkstra

用 Dijkstra 算法查找原始图中的所有可到达结点。

枚举每条边，计算有多少新结点（从原始边细分而来的新结点）是可达的。

代码 (C++)

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
struct Point
{
    int id;
    int shortest_path; // 到 0 的最短距离
    Point(int id = -1, int shortest_path = 0):id(id),shortest_path(shortest_path){}
};

struct Cmp
{
    bool operator()(const Point& p1, const Point& p2)
    {
        return p1.shortest_path > p2.shortest_path;
    }
};

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int M, int N) {
        vector<vector<PII> > g(N);
        for(const vector<int>& ijk: edges)
        {
            int i = ijk[0], j = ijk[1], k = ijk[2];
            g[i].push_back(PII(j, k + 1));
            g[j].push_back(PII(i, k + 1));
        }

        vector<int> d = dijkstra(g, 0);

        int result = 0;
        for(int i: d)
            if(i <= M)
                ++result;
        for(const vector<int>& edge: edges)
        {
            if(d[edge[0]] > M && d[edge[1]] > M)
                continue;
            else if(d[edge[0]] <= M && d[edge[1]] <= M)
                result += min(edge[2], 2 * M - d[edge[0]] - d[edge[1]]);
            else if(d[edge[0]] <= M)
                result += min(edge[2], M - d[edge[0]]);
            else
                result += min(edge[2], M - d[edge[1]]);
        }
        return result;
    }

private:
    using PII = pair<int, int>;
    vector<int> dijkstra(const vector<vector<PII> >& g, int start)
    {
        int N = g.size();
        vector<bool> visited(N, false);
        vector<int> d(N, INT_MAX);
        priority_queue<Point, vector<Point>, Cmp> q;
        q.push(Point(start, 0));
        while(!q.empty())
        {
            Point cur = q.top();
            q.pop();
            if(visited[cur.id]) continue;
            visited[cur.id] = true;
            d[cur.id] = cur.shortest_path;
            for(PII edge: g[cur.id])
            {
                int son_id = edge.first, len = edge.second;
                q.push(Point(son_id, cur.shortest_path + len));
            }
        }
        return d;
    }
};

1129. 颜色交替的最短路径

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。

给定两个数组 redEdges 和 blueEdges，其中：

  • redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边，
  • blueEdges[j] = [uj, vj] 表示图中存在一条从节点 uj 到节点 vj 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

提示：

1
2
3
4
1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= ai, bi, uj, vj < n

示例 1：
输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

示例 2：
输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

算法：dijkstra

在 dijkstra 的基础上，对每个点需要记录两种距离，一种是经过红色边进来的，一种是经过蓝色边进来的。

1
vector<vector<int>> d(2, vector<int>(n, INT_MAX / 2)); // d[c][i] := 经过c色边进入 i的 0 -> i 最短路径

代码 (C++)

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
struct EdgeTo
{
    int v;
    int color;
    EdgeTo(int v, int c):v(v),color(c){}
};

struct State
{
    int u;
    int d;
    int c;
    State(int u, int d, int c):u(u),d(d),c(c){}
};

struct HeapCmp
{
    bool operator()(const State& s1, const State& s2) const
    {
        return s1.d > s2.d;
    }
};

class Solution {
public:
    vector<int> dijkstra(vector<vector<EdgeTo>>& g, State s)
    {
        int n = g.size();
        priority_queue<State, vector<State>, HeapCmp> pq;
        pq.push(s);
        vector<vector<int>> d(2, vector<int>(n, INT_MAX / 2)); // d[c][i] := 经过c色边进入 i的 0 -> i 最短路径
        while(!pq.empty())
        {
            State cur = pq.top();
            pq.pop();
            if(d[cur.c][cur.u] != INT_MAX / 2)
                continue;
            d[cur.c][cur.u] = cur.d;
            for(EdgeTo &son: g[cur.u])
            {
                if(d[son.color][son.v] != INT_MAX / 2)
                    continue;
                if(son.color == cur.c)
                    continue;
                pq.push(State(son.v, cur.d + 1, son.color));
            }
        }
        vector<int> ans(n);
        for(int i = 0; i < n; ++i)
            ans[i] = min(d[0][i], d[1][i]);
        return ans;
    }

    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        vector<vector<EdgeTo>> g(n);
        for(vector<int> &e: red_edges)
            g[e[0]].emplace_back(e[1], 0);
        for(vector<int> &e: blue_edges)
            g[e[0]].emplace_back(e[1], 1);

        vector<int> d1 = dijkstra(g, State(0, 0, 0));
        vector<int> d2 = dijkstra(g, State(0, 0, 1));

        vector<int> ans(n);
        for(int i = 0; i < n; ++i)
        {
            ans[i] = min(d1[i], d2[i]);
            if(ans[i] == INT_MAX / 2)
                ans[i] = -1;
        }
        return ans;
    }
};

bellman ford

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

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

提示：

1
2
3
4
5
6
7
8
9
1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 1e4
航班没有重复，且不存在自环
0 <= src, dst, k < n
src != dst

示例 1：
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200

示例 2：
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500

算法：bellman ford

在 bellman ford 的基础上，K 站中转，相当于沿着邻接表的方向做了 K 次松弛，每次松弛的结果都要保存下来：

1
d[k][i] := 刚好 k 次松弛，i 点到 start 的最短距离

代码 (C++)

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
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<vector<int> > > g(n);
        for(vector<int> &flight: flights)
            g[flight[0]].push_back({flight[1], flight[2]});

        vector<vector<int> > d = bellman_ford(g, src, n, K + 1);

        int result = INT_MAX;
        for(int i = 1; i <= K + 1; ++i)
            if(d[i][dst] != -1)
                result = min(result, d[i][dst]);
        return result == INT_MAX ? -1 : result;
    }

private:
    vector<vector<int> > bellman_ford(vector<vector<vector<int> > >& g, int start, int N, int K)
    {
        vector<vector<int> > d(K + 1, vector<int>(N, -1));
        d[0][start] = 0;

        for(int cnt = 1; cnt <= K; ++cnt)
            for(int u = 0; u <= N - 1; ++u)
            {
                if(d[cnt - 1][u] == -1) continue;
                for(vector<int> &son: g[u])
                {
                    int v = son[0], w = son[1];
                    if(d[cnt - 1][u] + w < d[cnt][v] || d[cnt][v] == -1)
                        d[cnt][v] = d[cnt - 1][u] + w;
                }
            }

        return d;
    }
};

floyd

求最短哈密顿路

847. 访问所有节点的最短路径

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。

给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

提示：

1
2
3
4
5
6
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i] 不包含 i
如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
输入的图总是连通图

示例 1：
输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]

示例 2：
输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]

算法：Floyd + 状态压缩DP

Floyd + 状态压缩DP 求最短哈密顿路。

1
2
3
4
5
6
7
Floyd 求出 d[i][j]

dp[s][i] := 经过了 s 中的点，当前位置在 i 的最短路
枚举 s 中的点 i，枚举不在 s 中的点 j：
dp[s|(1 << j)][j] = min(dp[s][i] + d[i][j])

答案：使得 dp[(1 << n) - 1][i] 最小

代码 (C++)

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
40
41
42
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int N = graph.size();
        vector<vector<int> > d(N, vector<int>(N, INT_MAX / 2));
        for(int i = 0; i < N; ++i)
            for(int j: graph[i])
            {
                d[i][j] = 1;
                d[j][i] = 1;
            }
        for(int k = 0; k < N; ++k)
            for(int i = 0; i < N; ++i)
                for(int j = 0; j < N; ++j)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

        int all_state = (1 << N) - 1;
        vector<vector<int> > dp(all_state + 1, vector<int>(N, INT_MAX / 2));
        for(int i = 0; i < N; ++i)
            dp[(1 << i)][i] = 0;
        for(int state = 0; state < (1 << N); ++state)
        {
            for(int j = 0; j < N; ++j)
            {
                if(state & (1 << j)) continue;
                for(int i = 0; i < N; ++i)
                {
                    if(!(state & (1 << i))) continue;
                    // i 在 state 中，j 不在 state 中
                    dp[state|(1 << j)][j] = min(dp[state|(1 << j)][j], dp[state][i] + d[i][j]);
                }
            }
        }

        int result = INT_MAX;
        for(int i = 0; i < N; ++i)
            result = min(result, dp[(1 << N) - 1][i]);

        return result;
    }

};

求传递闭包

1462. 课程安排 IV

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你 必须 先选 ai 课程。

有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。
先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。

返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。

提示：

1
2
3
4
5
6
7
8
9
2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
每一对 [ai, bi] 都 不同
先修课程图中没有环。
0 <= ui, vi <= n - 1
ui != vi

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出：[false,true]
解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。

示例 2：
输入：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。

示例 3：
输入：numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出：[true,true]

算法：Floyd

本题是要求传递闭包。首先介绍一下传递闭包。在集合 $X$ 上的二元关系 $R$ 的传递闭包是包含 $R$ 的 $X$ 上的最小的传递关系。下面是两个例子：

  • 例如，如果 $X$ 是人的集合而 $R$ 是关系“为父子”，则 $R$ 的传递闭包是关系 “$x$ 是 $y$ 的祖先”。
  • 如果 $X$ 是空港的集合而关系 $xRy$ 为“从空港 $x$ 到空港 $y$ 有直航”，则 $R$ 的传递闭包是“可能经一次或多次航行从 $x$ 飞到 $y$”。

Floyd 可以用于求传递闭包，参考 343. 排序。

代码 (C++)

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
class Solution {
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<bool> > dp(n, vector<bool>(n, false));
        for(const vector<int>& prerequisite: prerequisites)
        {
            int i = prerequisite[0], j = prerequisite[1];
            dp[i][j] = true;
        }

        for(int k = 0; k < n; ++k)
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < n; ++j)
                    if(dp[i][k] && dp[k][j])
                        dp[i][j] = true;

        vector<bool> result;
        for(const vector<int>& query: queries)
        {
            int start = query[0], end = query[1];
            result.push_back(dp[start][end]);
        }
        return result;
    }
};
Share