出差(Bellman-Ford算法)
Bellman-Ford算法
1、问题描述
A 国有 N 个城市, 编号为1…N 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 N 的城市出差。
由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 N, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了 M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。
同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于小明之前在城市1, 因此可以直接离开城市 1 , 不需要隔离）
由于上级要求, 小明希望能够尽快赶到城市 N, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 N 。
输入格式
第 1 行: 两个正整数 N,M,N 表示 A 国的城市数量, M 表示末关闭的路 线数量
第 2 行: N 个正整数, 第 i 个整数
表示到达编号为 i 的城市后需要隔离 的时间
第 3…M+2 行: 每行 3 个正整数, u,v,c, 表示有一条城市 u 到城市 v 的 双向路线仍然开通着, 通过该路线的时间为 c
输出格式
第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 N 的最短时间（到达城市 N, 不需要计算城市 N 的隔离时间）
样例输入
4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5样例输出
13评测用例规模与约定
对于 100% 的数据, 1≤N≤1000,1≤M≤10000,1≤
≤200,1≤u,v≤N,1≤c≤1000
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
2、解题思路
从题意可知，这道题目考察的是最短路径的算法，碰到这种问题最容易想到的就是Floyd算法，三个for循环就写出来了，但是由于Floyd的时间复杂度是
，所以很容易超时，这里不考虑。
这种单源最短路径算法可以考虑
和
算法，我个人比较喜欢用
算法，这个算法通过枚举边，最多进行n-1次松弛操作并不断更新
数组，即可算出源点到每个点的最短路径。
Dijkstra算法的代码写起来比
稍微复杂，所以我倾向于使用
有关这两个算法的基础代码模板请看我以前的文章： Bellman-Ford算法–解决负权边问题 Dijkstra-单源最短路径算法
我们用数组g[i]表示到达i城市所需要隔离的时间。
由于存在隔离时间，所以我们每条边的权值需要有所调整，假设城市A到城市B有一条权值为w的双向边，那么我们从城市A到城市B的权值需要修改为
，从城市B到城市A的权值需要修改为
。
从A到B加上B的隔离时间 从B到A加上A的隔离时间
由于
算法是对边进行枚举，所以我们只需要在初始化的时候设置好边的权值即可，另外不需要考虑起点和终点的隔离时间。
g[n]=0;3、代码实现(AC)
package 国赛复习.迷宫;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BellmanFord {
public static List<int[]> edges=new ArrayList<>();
public static int[] dist;
public static int[] prev;
public static int[] g; //g[i]表示到达i城市需要隔离的时间
public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static void main(String[] args) throws IOException {
int n=nextInt();
int m=nextInt();
dist=new int[m+1];
prev=new int[m+1];
g=new int[n+1];
//每个城市的隔离时间
for (int i = 1; i <= n; i++) {
g[i]=nextInt();
}
g[n]=0; //终点的隔离时间不需要考虑
for (int i = 1; i <=m; i++) {
int u=nextInt();
int v=nextInt();
int c=nextInt();
//需要在权值的基础上加上隔离时间
edges.add(new int[]{u,v,c+g[v]});
edges.add(new int[]{v,u,c+g[u]});
}
//初始化
Arrays.fill(dist,Integer.MAX_VALUE>>1);
Arrays.fill(prev,-1);
int s=1;//起点
dist[s]=0;
for (int i =1; i <=n-1 ; i++) {
for (int[] edge : edges) {
int u=edge[0];
int v=edge[1];
int w=edge[2];
if(dist[u]+w<dist[v]){
dist[v]=dist[u]+w;
prev[v]=u;
}
}
}
System.out.println(dist[n]);
System.out.println(Arrays.toString(dist));
System.out.println(Arrays.toString(prev));
//输出从起点出发到每个点的最短路径
for (int i = 1; i <=n ; i++) {
print(s,i);
System.out.println();
}
}
//Bellman-Ford输出路径：倒着往回找路径，正着输出
public static void print(int start,int end){
if(start==end){
System.out.print(start+" ");
return;
}
print(start,prev[end]);//不断查找end的前驱，直到前驱节点为start
System.out.print(end+" ");
}
public static int nextInt() throws IOException{
st.nextToken();
return (int)st.nval;
}
}跑一个测试用例看看
输出从起点出发到每个点的最短路径(写个递归就行，逆着查前驱，正着输出)
这个代码是可以AC的
