JAVA—咖啡馆

——欢迎访问rogerfan的博客,常来《JAVA——咖啡馆》坐坐,喝杯浓香的咖啡,彼此探讨一下JAVA技术,交流工作经验,分享JAVA带来的快乐!本网站部分转载文章,如果有版权问题请与我联系。

BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

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

与传递闭包问题 非常相似的一个问题是,能不能给出一个矩阵,根据矩阵可以以时间代价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)

代码如下:

 

 1class Floyd {
 2    private int[][] adjMat;
 3    private static final int INFINITY = ~(1<<31);
 4
 5    Floyd(int size) {
 6        adjMat = new int[size][size];
 7        for(int i=0; i<size; i++)
 8            for(int j=0; j<size; j++)
 9                adjMat[i][j] = INFINITY;
10    }

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

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

27        
28    }

29
30    int[][] getConnections() {
31        return adjMat;
32    }

33
34    public static void main(String[] args) {
35        Floyd w = new Floyd(5);
36        w.connect(1,0,70);
37        w.connect(2,0,30);
38        w.connect(1,3,10);
39        w.connect(3,2,20);
40        for(int[] a: w.getConnections()) {
41            for(int i: a) System.out.print((i == INFINITY? "INF" : i) + "\t");
42            System.out.println();
43        }

44        w.floyd();
45        System.out.println("==================");
46        for(int[] a: w.getConnections()) {
47            for(int i: a) System.out.print((i == INFINITY? "INF" : i) + "\t");
48            System.out.println();
49        }

50    }

51}
posted on 2008-05-28 15:53 rogerfan 阅读(321) 评论(0)  编辑  收藏 所属分类: 【JAVA算法】

只有注册用户登录后才能发表评论。


网站导航: