代码高亮测试

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;
	}
}