当前位置：首页 > news >正文

Day53 | Bellman_ford 队列优化算法（又名SPFA）bellman_ford之判断负权回路 bellman_ford之单源有限最短路

news 2025/5/8 23:21:54

语言

Java

Bellman_ford 队列优化算法（又名SPFA）

题目

94. 城市间货物运输 I

题目描述

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

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

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

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

输出描述

如果能够从城市 1 到连通到城市 n，请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。

思路

定义 Edge 类：创建一个内部类 Edge 来表示图中的每条边，包含起点 from、终点 to 和边的权重 val。
构建邻接表：通过读取输入来构建一个邻接表 graph，其中每个节点是一个包含其所有出边的列表。
初始化距离数组：创建一个数组 minDist 来存储从起始节点（默认为 1）到每个节点的最短距离。所有节点的初始距离都设为 Integer.MAX_VALUE，除了起始节点设为 0。
使用队列优化节点选择：声明一个队列 queue 来存储待处理的节点，并使用一个布尔数组 isInQueue 来记录节点是否已经在队列中。这样可以避免重复加入队列。
循环处理队列中的节点：循环直到队列为空，每次从队列头部取出一个节点，对该节点的所有出边进行松弛操作。如果通过当前节点可以到达一个更短的距离，则更新该节点的距离，并将该节点加入队列（如果它还没有在队列中）。
结果输出：最后检查 minDist[n] 是否仍然为 Integer.MAX_VALUE，如果是，则表示不存在从起始节点到目标节点的路径；否则输出最短路径长度。

代码

import java.util.*;public class Main {// Define an inner class Edgestatic 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 processingScanner 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 nodeint[] 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 efficiencyQueue<Integer> queue = new LinkedList<>();queue.offer(1);// Declare a boolean array to record if the current node is in the queue to optimise the processingboolean[] isInQueue = new boolean[n + 1];while (!queue.isEmpty()) {int curNode = queue.poll();isInQueue[curNode] = false; // Represents the current node is not in the queue after being polledfor (Edge edge : graph.get(curNode)) {if (minDist[edge.to] > minDist[edge.from] + edge.val) { // Start relaxing the edgeminDist[edge.to] = minDist[edge.from] + edge.val;if (!isInQueue[edge.to]) { // Don't add the node if it's already in the queuequeue.offer(edge.to);isInQueue[edge.to] = true;}}}}// Outcome printingif (minDist[n] == Integer.MAX_VALUE) {System.out.println("unconnected");} else {System.out.println(minDist[n]);}}
}

易错点

代码假设起始节点总是 1，但在实际应用中，起始节点可能是任意一个节点。如果输入指定起始节点，需要相应修改代码

bellman_ford之判断负权回路

题目

95. 城市间货物运输 II

题目描述

然而，在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴，算法还需检测这种特殊情况。

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

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

输入描述

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

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

输出描述

如果没有发现负权回路，则输出一个整数，表示从城市 1 到城市 n 的最低运输成本（包括政府补贴）。如果该整数是负数，则表示实现了盈利。如果发现了负权回路的存在，则输出 "circle"。如果从城市 1 无法到达城市 n，则输出 "unconnected"。

思路

定义 Edge 类：创建一个内部类 Edge 来表示图中的每条边，包含起点 from、终点 to 和边的权重 val。
构建邻接表：通过读取输入来构建一个邻接表 graph，其中每个节点是一个包含其所有出边的列表。
初始化距离数组：创建一个数组 minDist 来存储从起始节点（默认为 1）到每个节点的最短距离。所有节点的初始距离都设为 Integer.MAX_VALUE，除了起始节点设为 0。
使用队列优化节点选择：声明一个队列 queue 来存储待处理的节点，并使用一个布尔数组 isInQueue 来记录节点是否已经在队列中。这样可以避免重复加入队列。
检测负权环：声明一个计数数组 count 来记录每个节点被加入队列的次数。如果某个节点被加入队列的次数超过了 n 次（即节点数量），则说明存在负权环。
循环处理队列中的节点：循环直到队列为空，每次从队列头部取出一个节点，对该节点的所有出边进行松弛操作。如果通过当前节点可以到达一个更短的距离，则更新该节点的距离，并将该节点加入队列（如果它还没有在队列中）。
结果输出：最后根据 minDist[n] 的值判断是否存在负权环或目标节点是否可达，并输出相应的结果。

代码

import java.util.*;public class Main {// 基于Bellman_ford-SPFA方法// Define an inner class Edgestatic 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 processingScanner 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 nodeint[] 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 efficiencyQueue<Integer> queue = new LinkedList<>();queue.offer(1);// Declare an array to record the times each node has been offered in the queueint[] count = new int[n + 1];count[1]++;// Declare a boolean array to record if the current node is in the queue to optimise the processingboolean[] isInQueue = new boolean[n + 1];// Declare a boolean value to check if there is a negative weight loop inside the graphboolean flag = false;while (!queue.isEmpty()) {int curNode = queue.poll();isInQueue[curNode] = false; // Represents the current node is not in the queue after being polledfor (Edge edge : graph.get(curNode)) {if (minDist[edge.to] > minDist[edge.from] + edge.val) { // Start relaxing the edgeminDist[edge.to] = minDist[edge.from] + edge.val;if (!isInQueue[edge.to]) { // Don't add the node if it's already in the queuequeue.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 timesflag = 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]);}}
}

易错点

如果检测到负权环，需要立即停止处理，并输出相应的信息。这里通过检查节点被加入队列的次数来判断是否存在负权环。

bellman_ford之单源有限最短路

题目

96. 城市间货物运输 III

题目描述

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本。

输入描述

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

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

最后一行包含三个正整数，src、dst、和 k，src 和 dst 为城市编号，从 src 到 dst 经过的城市数量限制。

输出描述

输出一个整数，表示从城市 src 到城市 dst 的最低运输成本，如果无法在给定经过城市数量限制下找到从 src 到 dst 的路径，则输出 "unreachable"，表示不存在符合条件的运输方案。

思路

定义 Edge 类：创建一个内部类 Edge 来表示图中的每条边，包含起点 from、终点 to 和边的权重 val。
输入处理：从标准输入读取节点数 n、边数 m、源节点 src、目标节点 dst 和最大迭代次数 k。然后读取每条边的信息并将其存储在 List<Edge> 中。
初始化距离数组：创建一个数组 minDist 来存储从源节点 src 到每个节点的最短距离。所有节点的初始距离都设为 Integer.MAX_VALUE，除了源节点 src 设为 0。
松弛操作：进行 k + 1 次松弛操作来更新 minDist 数组。每次迭代都会遍历所有边，并尝试通过每条边来减少到达目标节点的距离。为了保证每次迭代使用的是上一次迭代的结果，使用了一个临时数组 minDistCopy 来保存上一次迭代后的距离。
结果输出：最后检查 minDist[dst] 是否仍然为 Integer.MAX_VALUE，如果是，则表示不存在从源节点到目标节点的路径；否则输出最短路径长度。

代码

import java.util.*;public class Main {// 基于Bellman_for一般解法解决单源最短路径问题// Define an inner class Edgestatic 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 processingScanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();List<Edge> graph = new ArrayList<>();for (int i = 0; i < m; i++) {int from = sc.nextInt();int to = sc.nextInt();int val = sc.nextInt();graph.add(new Edge(from, to, val));}int src = sc.nextInt();int dst = sc.nextInt();int k = sc.nextInt();int[] minDist = new int[n + 1];int[] minDistCopy;Arrays.fill(minDist, Integer.MAX_VALUE);minDist[src] = 0;for (int i = 0; i < k + 1; i++) { // Relax all edges k + 1 timesminDistCopy = Arrays.copyOf(minDist, n + 1);for (Edge edge : graph) {int from = edge.from;int to = edge.to;int val = edge.val;// Use minDistCopy to calculate minDistif (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + val) {minDist[to] = minDistCopy[from] + val;}}}// Output printingif (minDist[dst] == Integer.MAX_VALUE) {System.out.println("unreachable");} else {System.out.println(minDist[dst]);}}
}