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


	


            
	    
    




            






            

				

            



    
    







            
	   
	



久久综合视频网站|
亚洲va久久久噜噜噜久久男同|
久久精品国产亚洲AV麻豆网站
|
一本久久精品一区二区|
欧美久久亚洲精品|
久久精品免费观看|
一本久久免费视频|
久久亚洲熟女cc98cm|
色婷婷综合久久久久中文一区二区|
99精品久久精品|
久久综合伊人77777|
国产人久久人人人人爽|
国产99久久九九精品无码|
久久久青草青青国产亚洲免观|
伊人色综合久久天天人手人婷|
国产精品久久久久9999|
欧美激情精品久久久久久久|
亚洲午夜久久久久久噜噜噜|
国产激情久久久久影院|
亚洲αv久久久噜噜噜噜噜|
一级做a爰片久久毛片16|
国产精品美女久久福利网站|
91久久精品电影|
久久99精品久久久久久hb无码|
色欲综合久久躁天天躁|
91久久成人免费|
久久久国产精品福利免费|
亚洲伊人久久大香线蕉综合图片|
久久久久这里只有精品|
久久综合久久综合久久|
久久婷婷五月综合国产尤物app|
思思久久好好热精品国产|
国产激情久久久久影院|
av无码久久久久不卡免费网站|
久久久亚洲欧洲日产国码是AV
|
伊人久久免费视频|
久久精品人人做人人爽97|
久久午夜免费视频|
欧美日韩精品久久久免费观看|
51久久夜色精品国产|
segui久久国产精品|