Skip to content

Latest commit

 

History

History
410 lines (292 loc) · 13.5 KB

0095.城市间货物运输II.md

File metadata and controls

410 lines (292 loc) · 13.5 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!

bellman_ford之判断负权回路

卡码网:95. 城市间货物运输 II

【题目描述】

某国为促进城市间经济交流,决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市,通过道路网络连接,网络中的道路仅允许从某个城市单向通行到另一个城市,不能反向通行。

网络中的道路都有各自的运输成本和政府补贴,道路的权值计算方式为:运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用;

权值为负则表示政府的补贴超过了支出的运输成本,实际表现为运输过程中还能赚取一定的收益。

然而,在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时,存在一种情况:图中可能出现负权回路

负权回路是指一系列道路的总权值为负,这样的回路使得通过反复经过回路中的道路,理论上可以无限地减少总成本或无限地增加总收益。

为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴,算法还需检测这种特殊情况。

请找出从城市 1 到城市 n 的所有可能路径中,综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

城市 1 到城市 n 之间可能会出现没有路径的情况

【输入描述】

第一行包含两个正整数,第一个正整数 n 表示该国一共有 n 个城市,第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行,每行包括三个整数,s、t 和 v,表示 s 号城市运输货物到达 t 号城市,道路权值为 v。

【输出描述】

如果没有发现负权回路,则输出一个整数,表示从城市 1 到城市 n 的最低运输成本(包括政府补贴)。

如果该整数是负数,则表示实现了盈利。如果发现了负权回路的存在,则输出 "circle"。如果从城市 1 无法到达城市 n,则输出 "unconnected"。

输入示例

4 4
1 2 -1
2 3 1
3 1 -1
3 4 1

输出示例

circle

思路

本题是 kama94.城市间货物运输I 延伸题目。

本题是要我们判断 负权回路,也就是图中出现环且环上的边总权值为负数。

如果在这样的图中求最短路的话, 就会在这个环里无限循环 (也是负数+负数 只会越来越小),无法求出最短路径。

所以对于 在有负权值的图中求最短路,都需要先看看这个图里有没有负权回路。

接下来我们来看 如何使用 bellman_ford 算法来判断 负权回路。

kama94.城市间货物运输I 中 我们讲了 bellman_ford 算法的核心就是一句话:对 所有边 进行 n-1 次松弛。 同时文中的 【拓展】部分, 我们也讲了 松弛n次以上 会怎么样?

在没有负权回路的图中,松弛 n 次以上 ,结果不会有变化。

但本题有 负权回路,如果松弛 n 次,结果就会有变化了,因为 有负权回路 就是可以无限最短路径(一直绕圈,就可以一直得到无限小的最短距离)。

那么每松弛一次,都会更新最短路径,所以结果会一直有变化。

(如果对于 bellman_ford 不了解的录友,建议详细看这里:kama94.城市间货物运输I

以上为理论分析,接下来我们再画图举例。

我们拿题目中示例来画一个图:

图中 节点1 到 节点4 的最短路径是多少(题目中的最低运输成本) (注意边可以为负数的)

节点1 -> 节点2 -> 节点3 -> 节点4,这样的路径总成本为 -1 + 1 + 1 = 1

而图中有负权回路:

那么我们在负权回路中多绕一圈,我们的最短路径 是不是就更小了 (也就是更低的运输成本)

节点1 -> 节点2 -> 节点3 -> 节点1 -> 节点2 -> 节点3 -> 节点4,这样的路径总成本 (-1) + 1 + (-1) + (-1) + 1 + (-1) + 1 = -1

如果在负权回路多绕两圈,三圈,无穷圈,那么我们的总成本就会无限小, 如果要求最小成本的话,你会发现本题就无解了。

在 bellman_ford 算法中,松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径,松弛 n 次以上,minDist数组(记录起到到其他节点的最短距离)中的结果也不会有改变 (如果对 bellman_ford 算法 不了解,也不知道 minDist 是什么,建议详看上篇讲解kama94.城市间货物运输I

而本题有负权回路的情况下,一直都会有更短的最短路,所以 松弛 第n次,minDist数组 也会发生改变。

那么解决本题的 核心思路,就是在 kama94.城市间货物运输I 的基础上,再多松弛一次,看minDist数组 是否发生变化。

代码和 kama94.城市间货物运输I 基本是一样的,如下:(关键地方已注释)

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2,权值为 val
        grid.push_back({p1, p2, val});

    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int> minDist(n + 1 , INT_MAX);
    minDist[start] = 0;
    bool flag = false;
    for (int i = 1; i <= n; i++) { // 这里我们松弛n次,最后一次判断负权回路
        for (vector<int> &side : grid) {
            int from = side[0];
            int to = side[1];
            int price = side[2];
            if (i < n) {
                if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) minDist[to] = minDist[from] + price;
            } else { // 多加一次松弛判断负权回路
                if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) flag = true;

            }
        }

    }

    if (flag) cout << "circle" << endl;
    else if (minDist[end] == INT_MAX) {
        cout << "unconnected" << endl;
    } else {
        cout << minDist[end] << endl;
    }
}
  • 时间复杂度: O(N * E) , N为节点数量,E为图中边的数量
  • 空间复杂度: O(N) ,即 minDist 数组所开辟的空间

拓展

本题可不可 使用 队列优化版的bellman_ford(SPFA)呢?

上面的解法中,我们对所有边松弛了n-1次后,在松弛一次,如果出现minDist出现变化就判断有负权回路。

如果使用 SPFA 那么节点都是进队列的,那么节点进入队列几次后 足够判断该图是否有负权回路呢?

0094.城市间货物运输I-SPFA 中,我们讲过 在极端情况下,即:所有节点都与其他节点相连,每个节点的入度为 n-1 (n为节点数量),所以每个节点最多加入 n-1 次队列。

那么如果节点加入队列的次数 超过了 n-1次 ,那么该图就一定有负权回路。

所以本题也是可以使用 SPFA 来做的。 代码如下:

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //邻接表
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); // 邻接表

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2,权值为 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int> minDist(n + 1 , INT_MAX);
    minDist[start] = 0;

    queue<int> que;
    que.push(start); // 队列里放入起点 
    
    vector<int> count(n+1, 0); // 记录节点加入队列几次
    count[start]++;

    bool flag = false;
    while (!que.empty()) {

        int node = que.front(); que.pop();

        for (Edge edge : grid[node]) {
            int from = node;
            int to = edge.to;
            int value = edge.val;
            if (minDist[to] > minDist[from] + value) { // 开始松弛
                minDist[to] = minDist[from] + value;
                que.push(to);
                count[to]++; 
                if (count[to] == n) {// 如果加入队列次数超过 n-1次 就说明该图与负权回路
                    flag = true;
                    while (!que.empty()) que.pop();
                    break;
                }
            }
        }
    }

    if (flag) cout << "circle" << endl;
    else if (minDist[end] == INT_MAX) {
        cout << "unconnected" << endl;
    } else {
        cout << minDist[end] << endl;
    }

}

其他语言版本

Java

import java.util.*;

public class Main {
    // 基于Bellman_ford-SPFA方法
    // Define an inner class Edge
    static class Edge {
        int from;
        int to;
        int val;
        public Edge(int from, int to, int val) {
            this.from = from;
            this.to = to;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        // Input processing
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<List<Edge>> graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int val = sc.nextInt();
            graph.get(from).add(new Edge(from, to, val));
        }

        // Declare the minDist array to record the minimum distance form current node to the original node
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;

        // Declare a queue to store the updated nodes instead of traversing all nodes each loop for more efficiency
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);

        // Declare an array to record the times each node has been offered in the queue
        int[] count = new int[n + 1];
        count[1]++;

        // Declare a boolean array to record if the current node is in the queue to optimise the processing
        boolean[] isInQueue = new boolean[n + 1];

        // Declare a boolean value to check if there is a negative weight loop inside the graph
        boolean flag = false;

        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            isInQueue[curNode] = false; // Represents the current node is not in the queue after being polled
            for (Edge edge : graph.get(curNode)) {
                if (minDist[edge.to] > minDist[edge.from] + edge.val) { // Start relaxing the edge
                    minDist[edge.to] = minDist[edge.from] + edge.val;
                    if (!isInQueue[edge.to]) { // Don't add the node if it's already in the queue
                        queue.offer(edge.to);
                        count[edge.to]++;
                        isInQueue[edge.to] = true;
                    }

                    if (count[edge.to] == n) { // If some node has been offered in the queue more than n-1 times
                        flag = true;
                        while (!queue.isEmpty()) queue.poll();
                        break;
                    }
                }
            }
        }

        if (flag) {
            System.out.println("circle");
        } else if (minDist[n] == Integer.MAX_VALUE) {
            System.out.println("unconnected");
        } else {
            System.out.println(minDist[n]);
        }
    }
}

Python

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    index = 0
    
    n = int(data[index])
    index += 1
    m = int(data[index])
    index += 1
    
    grid = []
    for i in range(m):
        p1 = int(data[index])
        index += 1
        p2 = int(data[index])
        index += 1
        val = int(data[index])
        index += 1
        # p1 指向 p2,权值为 val
        grid.append([p1, p2, val])

    start = 1  # 起点
    end = n    # 终点

    minDist = [float('inf')] * (n + 1)
    minDist[start] = 0
    flag = False

    for i in range(1, n + 1):  # 这里我们松弛n次,最后一次判断负权回路
        for side in grid:
            from_node = side[0]
            to = side[1]
            price = side[2]
            if i < n:
                if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
                    minDist[to] = minDist[from_node] + price
            else:  # 多加一次松弛判断负权回路
                if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
                    flag = True

    if flag:
        print("circle")
    elif minDist[end] == float('inf'):
        print("unconnected")
    else:
        print(minDist[end])

if __name__ == "__main__":
    main()

Go

Rust

Javascript

TypeScript

PhP

Swift

Scala

C#

Dart

C