• <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)  編輯 收藏 引用  所屬分類: 圖論 
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



熟妇人妻久久中文字幕|
欧美伊人久久大香线蕉综合|
久久久亚洲欧洲日产国码二区|
久久免费看黄a级毛片|
精品国产福利久久久|
久久久久免费视频|
久久久久亚洲精品天堂|
99久久99久久精品国产|
久久99精品久久久大学生|
色综合久久中文综合网|
久久久亚洲AV波多野结衣|
97精品国产97久久久久久免费|
成人午夜精品无码区久久|
国产精品欧美久久久久天天影视|
久久亚洲AV无码精品色午夜|
久久综合九色综合97_久久久|
亚洲人成网亚洲欧洲无码久久
|
精品久久久久久久久久中文字幕
|
国产成人久久精品一区二区三区|
久久高潮一级毛片免费|
久久精品一区二区国产|
精品久久久无码人妻中文字幕|
久久精品国产一区二区三区|
国产精品99精品久久免费|
AV无码久久久久不卡蜜桃|
久久99热这里只有精品66|
久久国产香蕉一区精品|
一本久久久久久久|
久久99国产精品尤物|
色综合久久无码五十路人妻|
国产成人无码精品久久久性色
|
色综合久久久久综合99|
久久不见久久见免费影院www日本|
人妻久久久一区二区三区|
亚洲熟妇无码另类久久久|
无码专区久久综合久中文字幕
|
亚洲中文字幕久久精品无码喷水|
人人狠狠综合久久亚洲|
亚洲国产精品无码久久九九|
亚洲Av无码国产情品久久|
久久久亚洲AV波多野结衣|