• <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 閱讀(2038) 評(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;
            }
            

            
	
            


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



亚洲国产精品成人久久蜜臀|
久久亚洲精品成人AV|
99热精品久久只有精品|
免费精品99久久国产综合精品|
国产精品久久成人影院|
久久久青草久久久青草|
久久99国产精品成人欧美|
中文精品99久久国产|
久久精品一区二区三区不卡|
精品无码久久久久久国产|
久久久久av无码免费网|
国产精品永久久久久久久久久
|
久久综合给久久狠狠97色|
99精品国产在热久久无毒不卡|
久久久黄片|
日本免费一区二区久久人人澡|
中文字幕日本人妻久久久免费
|
一本一本久久a久久精品综合麻豆|
久久精品中文字幕无码绿巨人|
久久精品国产一区二区三区不卡|
久久国产亚洲高清观看|
伊人久久大香线蕉综合热线|
久久久久免费精品国产|
无码AV波多野结衣久久|
久久夜色精品国产噜噜亚洲a|
亚洲国产精品久久久久久|
无码人妻精品一区二区三区久久|
亚洲人成网站999久久久综合|
国产精品视频久久久|
国产成人久久精品激情|
久久精品日日躁夜夜躁欧美|
亚洲AV伊人久久青青草原|
久久国产精品免费一区二区三区|
精品久久久久香蕉网|
久久亚洲日韩精品一区二区三区|
久久久久久伊人高潮影院|
伊人久久成人成综合网222|
日本精品久久久久久久久免费|
国产精品狼人久久久久影院
|
久久精品国产网红主播|
久久久久久九九99精品|