<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 閱讀(402) 評論(0)  編輯  收藏 所屬分類: 【JAVA算法】
    主站蜘蛛池模板: 亚洲人成无码网WWW| 免费毛片在线播放| 国产亚洲综合色就色| 一级毛片免费毛片毛片| 亚洲国产成人影院播放| 香蕉97碰碰视频免费| 国产一级淫片a视频免费观看| 亚洲AV综合色区无码一二三区| 成年大片免费视频| 亚洲AV成人一区二区三区观看 | 亚洲高清毛片一区二区| 免费av欧美国产在钱| 77777午夜亚洲| 国产成人免费A在线视频| 一级做a毛片免费视频| 亚洲热线99精品视频| 13小箩利洗澡无码视频网站免费 | 亚洲中文字幕伊人久久无码| 国产高潮流白浆喷水免费A片 | 亚洲色婷婷综合久久| 一区二区三区四区免费视频| 亚洲午夜电影在线观看高清| 午夜老司机免费视频| 国产成人久久精品亚洲小说| MM131亚洲国产美女久久 | 人妻巨大乳hd免费看| 国产乱辈通伦影片在线播放亚洲 | 亚洲国产成人精品电影| 在线日韩av永久免费观看| 一级人做人爰a全过程免费视频| 亚洲国产成人一区二区三区| 久久WWW免费人成一看片| 亚洲av无码一区二区三区天堂 | 亚洲日韩精品一区二区三区无码| 久久永久免费人妻精品下载| 亚洲资源最新版在线观看| www国产亚洲精品久久久日本| 免费国产午夜高清在线视频 | 国产亚洲精品仙踪林在线播放| 亚洲无线码一区二区三区| 免费不卡视频一卡二卡|