应用场景：带有负权边的图
为什么dijkstra算法不能计算带有负权边图
答：
dijkstra是一拳头买卖，一条边就经过一次，如果有负权边显然如果遍历多次这条边，最小值绝s对会更小。
所以bellman_ford算法大多的应用场景是在经过的边数有限制的情况下（能多次经过负权边但是有次数限制）
dijkstra算法(简介)：
思路：
从源点开始(初始化为距离为0的那个点)也是自己确定的最小距离点
循环n(顶点数)次每一次确定一个距离最小值点，再用最小值点更新孩子节点，循环n次确定n个最小值点
通过点来更新其孩子(边只走一次)
bellman_ford算法
思路：
遍历n次，每次遍历所有的边，然后以父节点更新其出边(孩子节点)
遍历所有的边所以会遍历某个点的所有的入边，根据dist[i] + w[i] 和dist[x]该点的值]递推，即可得到最短距离
遍历n次所有的边，可以多次经过统一条边(可计算最大经过边数的最短路径(当有负权环的时候必须限定最大经理经历边数不然最小距离为负无穷))
代码：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N = 510; static int M = 100010; static int n;//总点数 static int m;//总边数 static int[] dist = new int[N];//从1到点到n号点的距离 static Node[] list = new Node[M];//结构体 static int INF = 500000000 + 5000000; public static void bellman_ford() { Arrays.fill(dist, INF); dist[1] = 0; //最长可能的最短路径不会超过n-1条边 循环n - 1次也就是最多经过n - 1条边 for(int i = 0;i < n - 1;i++) { for(int j = 0;j < m;j++) { Node node = list[j]; int a = node.a; int b = node.b; int c = node.c; dist[b] = Math.min(dist[b], dist[a] + c); } } if(dist[n] >= 500000000) System.out.println("-1"); else System.out.println(dist[n]); } public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] str1 = reader.readLine().split(" "); n = Integer.parseInt(str1[0]); m = Integer.parseInt(str1[1]); for(int i = 0;i < m;i++) { String[] str2 = reader.readLine().split(" "); int a = Integer.parseInt(str2[0]); int b = Integer.parseInt(str2[1]); int c = Integer.parseInt(str2[2]); list[i] = new Node(a,b,c); } bellman_ford(); } } class Node { int a, b, c; public Node(int a,int b,int c) { this.a = a; this.b = b; this.c = c; } }
增加功能检测负权回路(不存在最短路径)
for (int i = 0; i < n; i++) { int u = edges[i].source; int v = edges[i].destination; int w = edges[i].weight; //经过n条边，如果可以更新毕然存在负权回路 if (distance[u] != Integer.MAX_VALUE && distance[u] + w < distance[v]) { System.out.println("图中包含负权回路"); return; } }
