• <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中文字幕无码久久久妻妇|
久久久久女教师免费一区|
亚洲人成电影网站久久|
国产成人精品综合久久久久|
久久亚洲日韩精品一区二区三区
|
久久天天躁狠狠躁夜夜2020老熟妇|
人人狠狠综合久久亚洲高清|
精产国品久久一二三产区区别|
久久精品国产亚洲av高清漫画
|
国内精品久久久久久久久|
亚洲国产成人久久笫一页|
久久精品国产网红主播|
久久激情五月丁香伊人|
久久综合88熟人妻|
久久亚洲欧洲国产综合|
AV无码久久久久不卡网站下载
|
久久天天躁狠狠躁夜夜网站|
国产精品免费久久久久电影网|
久久人人爽人人爽人人片AV麻烦|
久久99免费视频|
亚洲中文精品久久久久久不卡|
精品人妻伦一二三区久久|
久久久国产精品亚洲一区|
香蕉久久夜色精品国产2020|
久久99精品久久久久久噜噜|
99久久精品国产免看国产一区|
中文字幕亚洲综合久久菠萝蜜|
国产免费福利体检区久久|
狠狠色丁香久久婷婷综合五月|
久久久久久久久久久|
精品国产乱码久久久久久浪潮|
91久久精品91久久性色|
97久久精品人妻人人搡人人玩|
囯产极品美女高潮无套久久久|
四虎国产精品成人免费久久|
久久久久久亚洲精品不卡|
国产综合免费精品久久久|