Ex 4_10 给定一个有向图G=(V,E),其中边...(bellman-ford算法的应用)..

在bellman-ford算法中,循环n-1(n为顶点个数)次可以找出从源点到其他顶点的最多n-1条边的最短路径，若循环k次则可以找出从源点到其他顶点的最多k条边的最短路径。

 1 package org.xiu68.ch04.ex12;
 2 
 3 public class Ex4_10 {
 4     public static void main(String[] args) {
 5         int[][] edges=new int[][]{
 6             {0,10,0,4,1},
 7             {0,0,0,0,0},
 8             {0,-10,0,0,0},
 9             {0,0,0,0,0},
10             {0,0,2,0,0}
11         };
12         MGraph m1=new MGraph(edges);
13         m1.bellmanFord(0,2);
14     }
15 }
16 
17 class MGraph{
18     private int[][] edges;        //有向图边集
19     private int vexNum;            //顶点数目
20     private int[] dist;            //源点到该顶点的距离
21     private int maxDistant;        //表示距离无穷远
22     
23     public MGraph(int[][] edges){
24         this.edges=edges;
25         this.vexNum=edges.length;
26         this.dist=new int[vexNum];
27         this.maxDistant=1000000;
28     }
29     
30     public void bellmanFord(int start,int edgeNum){
31         //初始化dist数组
32         for(int i=0;i<vexNum;i++){
33                 dist[i]=maxDistant;
34         }
35         dist[start]=0;
36         
37         for(int i=0;i<edgeNum;i++){                //从源点到任何一个顶点的最多edgeNum条边的最短路径
38             boolean flag=false;                    //记录在本次循环中从源点到某个顶点是否有更短的路径
39             //遍历所有的边
40             for(int j=0;j<vexNum;j++){            
41                 for(int k=0;k<vexNum;k++){
42                     if(edges[j][k]!=0 && dist[k]>dist[j]+edges[j][k]){
43                         dist[k]=dist[j]+edges[j][k];
44                         flag=true;
45                     }
46                 }
47             }
48             if(flag==false)        //已经求得所有顶点最多edgeNum条边的最短路径
49                 break;
50         }
51         
52         /*
53         //本次循环检测是否有负环存在
54         //从源点到某个顶点有n条边,且路径更短,说明有负环存在
55         for(int i=0;i<vexNum;i++){
56             for(int j=0;j<vexNum;j++){
57                 if(edges[i][j]!=0 && dist[j]>dist[i]+edges[i][j])
58                     return false;
59             }
60         }
61         */
62         
63         for(int i=0;i<vexNum;i++)
64             System.out.println(i+":"+dist[i]);
65     }
66 }

View Code


package org.xiu68.ch04.ex12;

public class Ex4_10 {
	public static void main(String[] args) {
		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);
		m1.bellmanFord(0,2);
	}
}

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 void bellmanFord(int start,int edgeNum){
		//初始化dist数组
		for(int i=0;i<vexNum;i++){
				dist[i]=maxDistant;
		}
		dist[start]=0;
		
		for(int i=0;i<edgeNum;i++){				//从源点到任何一个顶点的最多edgeNum条边的最短路径
			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)		//已经求得所有顶点最多edgeNum条边的最短路径
				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]);
	}
}

Ex 4_10 给定一个有向图G=(V,E),其中边...(bellman-ford算法的应用).._第十二次作业

推荐阅读