图－每一对端点间的最小距离

与传递闭包问题 非常相似的一个问题是，能不能给出一个矩阵，根据矩阵可以以时间代价O(n)的方式得到在一个有向代权图中任意指定端点之间的最短距离。求的这个矩阵的问题被称为每一对端点间的最小距离问题。

这里采用的是Floyd算法，它与WalShall 算法非常相似：

如果A可以到达B，距离为x，且C可以到达A，距离为y，则求得C可以到达B，距离为 z = x + y，z小于如果c到B的原来的距离，则用z更新矩阵，否则c到B距离维持不变。

和最小路径算法类似，这里用一个很大数字INFINITY来表示两个端点之间距离为无穷大的情况，即不通。这里INFINITY＝最大的int值(~(1<<31))。

Floyd.main()提供简单的测试。

与WalShall 一样，Floyd算法本身的时间代价为O(n^3)

代码如下：

class Floyd {
	private int[][] adjMat;
	private static final int INFINITY = ~(1<<31);

	Floyd(int size) {
		adjMat = new int[size][size];
		for(int i=0; i<size; i++)
			for(int j=0; j<size; j++)
				adjMat[i][j] = INFINITY;
	}

	void connect(int from, int to, int length) {
		adjMat[from][to] = length;
	}

	void floyd() { //floyd算法
		for(int y=0; y<adjMat.length; y++) //查找每一行
			for(int x=0; x<adjMat.length; x++) // 查找每个单元格
				if(adjMat[y][x] != INFINITY)	//如果 y 可以到达 x
					for(int z=0; z<adjMat.length; z++)	//查找所有行的y列
						//如果 z 可以到达y ，说明z
						//可以直接到达x,如果算出来的新距离小于原来的距离，则更新
						if(adjMat[z][y] != INFINITY) {
							int newLength = adjMat[z][y] + adjMat[y][x];
							adjMat[z][x] = newLength < adjMat[z][x] ? newLength : adjMat[z][x];	
						}
		
	}

	int[][] getConnections() {
		return adjMat;
	}

	public static void main(String[] args) {
		Floyd w = new Floyd(5);
		w.connect(1,0,70);
		w.connect(2,0,30);
		w.connect(1,3,10);
		w.connect(3,2,20);
		for(int[] a: w.getConnections()) {
			for(int i: a) System.out.print((i == INFINITY? "INF" : i) + "\t");
			System.out.println();
		}
		w.floyd();
		System.out.println("==================");
		for(int[] a: w.getConnections()) {
			for(int i: a) System.out.print((i == INFINITY? "INF" : i) + "\t");
			System.out.println();
		}
	}
}

 

评论

4 楼 comsci 2009-02-23  

有这么一个需求，求图中任意两个节点直接的关系，所谓的关系就是指，其一节点是否是另外一个节点的分支点(分支的次数不限)

3 楼 longshou 2008-05-26  

   

2 楼 longshou 2008-05-26  

            

1 楼 pf_miles 2008-05-26  

你这个所有边的权都是正值吗？如果是，那就用Dijkstra最短路径算法要好一些，时间复杂度是O(n^2)