图－每一对端点间的最小距离
与传递闭包问题非常相似的一个问题是，能不能给出一个矩阵，根据矩阵可以以时间代价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;for(int i=0; i<size; i++)for(int j=0; j<size; j++)adjMat = INFINITY;}void connect(int from, int to, int length) {adjMat = length;}void floyd() { //floyd算法for(int y=0; y<adjMat.length; y++) //查找每一行for(int x=0; x<adjMat.length; x++) // 查找每个单元格if(adjMat != INFINITY)//如果 y 可以到达 xfor(int z=0; z<adjMat.length; z++)//查找所有行的y列//如果 z 可以到达y ，说明z//可以直接到达x,如果算出来的新距离小于原来的距离，则更新if(adjMat != INFINITY) {int newLength = adjMat + adjMat;adjMat = newLength < adjMat ? newLength : adjMat;}}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();}}}
页:
[1]