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

    
            

            




            







												


        

            
	

            yuanyuelang
            

            

            


            
	
		

            常用鏈接
            

		

            統計
            
	
		
		

		

            最新評論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			每對頂點間的最短路徑之Floyd-Warshall算法
		
            
		        Floyd-Warshall算法的基本思路是：
               1.用D[v][w]記錄每對頂點間的最短距離
               2.對每一個圖中的頂點，以其作為基點掃描每一對D[v][w]，檢驗是否通過該基點可以使得這對頂點間的距離變小。

            我們實際是很容易就可以寫出這個算法的代碼：

            

            #define N 100
            void Floyd(int dist[N][N],int n)
            {
                          int i,j,k;
                          for(k=0;k<n;k++)
                            for(i=0;i<n;i++)
                              for(j=0;j<n;j++)
                                if(dist[i][k]+dist[k][j]<dist[i][j])
                       dist[i][j]            =dist[i][k]+dist[k][j];
                    
            }
              
            

            

            我們還面臨一個保存路徑的問題,如何來做呢？
            

            #define N 100
            int map[N][N];
            void Floyd(int dist[N][N],int path[N][N],int n)
            {
                          int i,j,k;
                          for(i=0;i<n;i++)
                            for(j=0;j<n;j++)
                  dist[i][j]            =map[i][j],path[i][j]=0;
                          for(k=0;k<n;k++)
                            for(i=0;i<n;i++)
                              for(j=0;j<n;j++)
                                if(dist[i][k]+dist[k][j]<dist[i][j]){
                       dist[i][j]            =dist[i][k]+dist[k][j];
                       path[i][j]            =k;
                    
            }

            void output(int i,int j)
            {
                          if(i==j) return;
                          if(path[i][j]==0) cout<<j<<" ";
                          else{
                output(i,path[i][j]);
                output(path[i][j],j);
              }
            }
              
            

            

		
            
			posted on 2009-09-23 11:35 原語餓狼 閱讀(360) 評論(0)  編輯 收藏 引用  所屬分類: 圖論 
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



国产精品免费福利久久|
精品免费久久久久国产一区|
久久综合亚洲鲁鲁五月天|
久久久久亚洲AV成人网人人网站
|
久久天天躁狠狠躁夜夜av浪潮|
精品国产青草久久久久福利|
久久婷婷五月综合97色一本一本
|
人人狠狠综合久久亚洲婷婷|
国产一区二区精品久久岳|
少妇无套内谢久久久久|
国产精品久久久久影院嫩草|
日韩亚洲国产综合久久久|
69国产成人综合久久精品|
国产精品久久新婚兰兰|
国内精品欧美久久精品|
久久午夜无码鲁丝片|
亚洲精品美女久久久久99小说
|
三级三级久久三级久久|
精品久久777|
亚洲精品成人网久久久久久|
久久99久久99小草精品免视看|
欧美伊人久久大香线蕉综合|
久久www免费人成精品香蕉|
99久久国产热无码精品免费|
麻豆av久久av盛宴av|
色老头网站久久网|
久久精品一区二区影院|
91亚洲国产成人久久精品|
www久久久天天com|
97久久综合精品久久久综合|
一本久久a久久精品vr综合|
国产精品久久久久久久人人看
|
91精品国产综合久久四虎久久无码一级|
精品久久久无码人妻中文字幕|
亚洲国产一成久久精品国产成人综合
|
69国产成人综合久久精品|
久久国产精品99国产精|
久久精品国产网红主播|
av无码久久久久不卡免费网站|
久久66热人妻偷产精品9|
精品熟女少妇a∨免费久久|