【问题描述】
对于一个带负权值边的有向图，实现Bellman-Ford算法，求出从指定顶点s到其余顶点的最短路径，并判断图中是否存在负环。
package org.xiu68.exp.exp10;
public class Exp10_1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] edges=new int[][]{
{0,10,0,4,1},
{0,0,0,0,0},
{0,-10,0,0,0},
{0,0,0,0,0},
{0,0,2,0,0}
};
MGraph m1=new MGraph(edges);
System.out.println(m1.bellmanFord(0));
}
}
class MGraph{
private int[][] edges; //有向图边集
private int vexNum; //顶点数目
private int[] dist; //源点到该顶点的距离
private int maxDistant; //表示距离无穷远
public MGraph(int[][] edges){
this.edges=edges;
this.vexNum=edges.length;
this.dist=new int[vexNum];
this.maxDistant=1000000;
}
public boolean bellmanFord(int start){
//初始化dist数组
for(int i=0;i<vexNum;i++){
dist[i]=maxDistant;
}
dist[start]=0;
for(int i=0;i<vexNum-1;i++){ //从源点到任何一个顶点的最短路径最多有n-1条边
boolean flag=false; //记录在本次循环中从源点到某个顶点是否有更短的路径
//遍历所有的边
for(int j=0;j<vexNum;j++){
for(int k=0;k<vexNum;k++){
if(edges[j][k]!=0 && dist[k]>dist[j]+edges[j][k]){
dist[k]=dist[j]+edges[j][k];
flag=true;
}
}
}
if(flag==false) //已经求得所有顶点的最短路径
break;
}
//本次循环检测是否有负环存在
//从源点到某个顶点有n条边,且路径更短,说明有负环存在
for(int i=0;i<vexNum;i++){
for(int j=0;j<vexNum;j++){
if(edges[i][j]!=0 && dist[j]>dist[i]+edges[i][j])
return false;
}
}
for(int i=0;i<vexNum;i++)
System.out.println(i+":"+dist[i]);
return true;
}
}