• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            
	
            
		
			

            

            
	
            
		
			
            lzm
            
			who dare win.
		            		
	
            

            

            

            

            posts - 14, comments - 29, trackbacks - 0, articles - 0
            


            		
	
            
	
            
		
			
		
		
			
            
				
					
	
            
		
            
			
            
				Floyd_Warshall算法
			
            
 			Posted on 2009-04-11 03:14 lzmagic 閱讀(2046) 評(píng)論(0)  編輯 收藏 引用  所屬分類: Algorithm 
			
			


		
            
		
            /**
             * FLOYD_WARSHALL 所有頂點(diǎn)對(duì)的最短路徑算法 (All-Pairs Shortest Path Algorithm)
             * 輸入：圖g
             * 輸出：所有頂點(diǎn)對(duì)的最短路徑長(zhǎng)
             * 結(jié)構(gòu)：圖g用鄰接矩陣表示
             * 算法：Floyd_Warshall算法(動(dòng)態(tài)規(guī)劃)
             * 復(fù)雜度：O(|V|^3) 
                         */
            #include             <iostream>
            #include             <string>
            #include             <vector>
            #include             <deque>
            #include             <list>
            #include             <stack>
            #include             <queue>
            #include             <iterator>
            #include             <algorithm>
            #include             <numeric>
            #include             <functional>
            #include             <climits>
            using namespace std;

            int n;
            vector            <vector<int> > g;
            vector            <vector<int> > dist;

            void Floyd_Warshall()
            {
                            // 初始化dist，頂點(diǎn)間(無(wú)中間頂點(diǎn))最短路徑長(zhǎng)為邊長(zhǎng)，頂點(diǎn)到自身的最短路徑長(zhǎng)為0。 
                dist = g;
                            for (int i = 0; i < n; ++i)  
                    dist[i][i]             = 0;
                            // 從頂點(diǎn)i到定點(diǎn)j且中間頂點(diǎn)皆屬于集合{0, 1, 2, , k}的最短路徑長(zhǎng)。 
                for (int k = 0; k < n; ++k)
                                for (int i = 0; i < n; ++i)
                                    for (int j = 0; j < n; ++j)
                                        if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX)
                                dist[i][j]             = min(dist[i][j], dist[i][k] + dist[k][j]);
            }

            int main()
            {
                n             = 5;    
                g.assign(n, vector            <int>(n, INT_MAX));
                g[            0][1] = 3; g[0][2] = 8; g[0][4] = -4;
                g[            1][3] = 1; g[1][4] = 7;
                g[            2][1] = 4; 
                g[            3][0] = 2; g[3][2] = -5;
                g[            4][3] = 6;
                 
                Floyd_Warshall();
                
                            for (int i = 0; i < n; ++i)
                            {
                                for (int j = 0; j < n; ++j)
                        cout             << dist[i][j] << ' ';
                    cout             << endl;        
                }
                
                system(            "pause");
                            return 0;
            }
            

            
	
            


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



久久婷婷久久一区二区三区|
天天影视色香欲综合久久|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
手机看片久久高清国产日韩|
色欲综合久久躁天天躁|
亚洲狠狠婷婷综合久久蜜芽|
亚洲精品午夜国产va久久|
久久99国产亚洲高清观看首页|
亚洲综合熟女久久久30p|
亚洲αv久久久噜噜噜噜噜|
99久久国语露脸精品国产|
亚洲成色999久久网站|
国内精品久久久久久中文字幕|
欧美成人免费观看久久|
亚洲精品国产成人99久久|
色偷偷偷久久伊人大杳蕉|
欧美精品福利视频一区二区三区久久久精品
|
亚洲日本va午夜中文字幕久久|
久久无码人妻一区二区三区
|
九九久久精品国产|
精品人妻久久久久久888|
欧美久久久久久|
99久久成人国产精品免费|
久久久久免费视频|
久久无码av三级|
久久99精品久久久久久动态图|
热综合一本伊人久久精品|
一本久久久久久久|
久久久久亚洲Av无码专|
精品无码久久久久国产动漫3d|
久久国产一片免费观看|
狠狠色丁香久久婷婷综|
亚洲综合伊人久久综合|
伊人久久综合成人网|
精品久久久久久久久免费影院
|
狠狠人妻久久久久久综合蜜桃
|
久久综合伊人77777|
久久久久久久综合日本|
久久精品日日躁夜夜躁欧美|
久久受www免费人成_看片中文|
欧美久久天天综合香蕉伊|