• <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;
            }
            

            
	
            


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



99久久无码一区人妻|
午夜精品久久久久久久无码|
国产精品久久久久久福利漫画
|
品成人欧美大片久久国产欧美
|
亚洲AⅤ优女AV综合久久久|
久久午夜夜伦鲁鲁片免费无码影视|
色综合久久久久久久久五月|
热久久国产精品|
久久久国产打桩机|
久久久久久毛片免费看|
国内精品久久久久久99|
国产精品亚洲综合久久|
国产69精品久久久久9999|
日韩精品久久无码人妻中文字幕|
国产成人综合久久久久久|
少妇高潮惨叫久久久久久|
久久亚洲2019中文字幕|
九九99精品久久久久久|
久久人人爽人人爽人人AV东京热|
亚洲伊人久久综合影院|
精品国产综合区久久久久久
|
99久久香蕉国产线看观香|
国产精品久久久久乳精品爆|
成人资源影音先锋久久资源网|
久久精品中文字幕大胸|
久久久久久久亚洲精品|
精品多毛少妇人妻AV免费久久|
久久不射电影网|
久久久久人妻一区二区三区|
7777久久久国产精品消防器材|
久久精品国产国产精品四凭
|
精品一区二区久久久久久久网站|
人妻精品久久无码区|
久久久亚洲欧洲日产国码二区|
伊人精品久久久久7777|
国产精品岛国久久久久|
AAA级久久久精品无码片|
久久综合精品国产二区无码|
人妻精品久久无码区|
jizzjizz国产精品久久|
99久久精品国产一区二区蜜芽|