<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    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 閱讀(406) 評論(0)  編輯  收藏 所屬分類: 【JAVA算法】
    主站蜘蛛池模板: 日本免费人成网ww555在线| 亚洲热妇无码AV在线播放| 日韩午夜理论免费TV影院| 亚洲av无码专区国产不乱码| 亚洲AV无码欧洲AV无码网站| 国产无遮挡又黄又爽免费视频| 亚洲中文字幕久久久一区| 亚洲国产综合专区在线电影| 亚洲国产综合人成综合网站| 成人毛片18女人毛片免费96| 无码国产精品一区二区免费16| 国产精品偷伦视频免费观看了| 亚洲AV无码一区二区三区久久精品| 亚洲喷奶水中文字幕电影| 亚洲AV无码专区电影在线观看 | 在线A亚洲老鸭窝天堂| 又粗又黄又猛又爽大片免费| 日本一区二区三区免费高清| 91久久青青草原线免费| 免费视频精品一区二区三区| 中文字幕在线免费观看视频| 一级女性全黄久久生活片免费| 亚洲AV成人一区二区三区观看| 亚洲欧美成人一区二区三区 | 成年人网站在线免费观看| 国产精品怡红院永久免费| 50岁老女人的毛片免费观看| 国产成人久久AV免费| 男人j进入女人j内部免费网站| 91在线视频免费观看| 97无码人妻福利免费公开在线视频 | 亚洲综合一区二区| 久久亚洲精品成人无码网站| 亚洲精品免费观看| 4480yy私人影院亚洲| 亚洲精品视频免费在线观看| 亚洲精品自拍视频| 亚洲中文字幕久久无码| 亚洲国产精品18久久久久久| 亚洲AV无码资源在线观看| 免费人成网上在线观看|