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