【笔记】数据结构与算法之最短路算法（Bellman_Ford）
适用于存在负权边的情况下import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static class Edge{
int a,b,w;
Edge(int a,int b ,int w){
this.a = a;
this.b = b;
this.w = w;
}
}
static int M = 100010;
private static int N= 510,INF= 0x3f3f3f3f;
staticEdge [] edges = new Edge;
static int[] dist = new int;
static int[] backup = new int;
static int n,m,k;
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s = bf.readLine().split(" ");
// 总共n个点m条边且顶多经过k条边
n = Integer.parseInt(s);
m = Integer.parseInt(s);
k = Integer.parseInt(s);
for (int i = 0; i < m; i++) {
String []re = bf.readLine().split(" ");
//分别是第一条边和第二条边
int a = Integer.parseInt(re);
int b = Integer.parseInt(re);
//距离
int w = Integer.parseInt(re);
edges = new Edge(a,b,w);
}
int res = bellmanFord();
//找不到最短路，例如有负权边进入死循环导致正无穷大
if (res==-1){
System.out.println("impossible");
}else {
System.out.println(res);
}
}
private static int bellmanFord() {
//初始化操作
Arrays.fill(dist,INF);
dist = 0;
//循环顶多进行k次
for (int i = 0; i < k; i++) {
backup = dist.clone();
for (int j = 0; j < m; j++) {
int a = edges.a;
int b = edges.b;
int w = edges.w;
//使用备份去避免串联，用无穷大来更新，取得最小值
dist = Math.min(dist,backup+w);
}
}
//因为有最大值INF,还有负权，加上负权边可能不是INF了，可能比INF小，所以判断大于一半就行
if (dist>INF/2){
return -1;
}
return dist;
}
}
在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中
页:
[1]