<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算法】
    主站蜘蛛池模板: 亚洲视频网站在线观看| 亚洲黄页网在线观看| 牛牛在线精品观看免费正| 在线看片人成视频免费无遮挡| 黄色永久免费网站| 久久精品国产亚洲AV麻豆网站 | 国产免费av一区二区三区| 亚洲日韩av无码| 成人精品视频99在线观看免费| 国产乱辈通伦影片在线播放亚洲| 亚洲国产香蕉碰碰人人| 99精品视频在线视频免费观看 | 一本色道久久综合亚洲精品高清 | 久久免费观看国产精品| 亚洲男人天堂av| 99在线精品视频观看免费| 亚洲一区二区三区高清不卡| 韩国日本好看电影免费看| 美女啪啪网站又黄又免费| 在线观看亚洲av每日更新| 亚洲免费在线视频| 亚洲人成网站看在线播放| 国产免费无遮挡精品视频| 国产人成网在线播放VA免费| 亚洲电影在线免费观看| 亚洲乱亚洲乱妇24p| 91热成人精品国产免费| 亚洲熟妇久久精品| 久久久久国产成人精品亚洲午夜| 免费人成网站在线观看不卡| 亚洲毛片av日韩av无码| 久久免费高清视频| 亚洲色大成网站WWW国产| 国产精品V亚洲精品V日韩精品| 久久久免费的精品| 亚洲AV无码一区二区一二区| 可以免费看的卡一卡二| 91亚洲自偷手机在线观看| 日韩毛片免费在线观看| a级毛片在线免费观看| 亚洲人成77777在线观看网|