• <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 原語餓狼 閱讀(359) 評論(0)  編輯 收藏 引用  所屬分類: 圖論 
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



久久99国产精品成人欧美|
久久久久久精品久久久久|
精品熟女少妇a∨免费久久|
A狠狠久久蜜臀婷色中文网|
久久精品国产91久久麻豆自制|
久久精品国产久精国产|
久久中文精品无码中文字幕|
久久精品亚洲精品国产色婷|
久久人人爽人人精品视频|
国产成人精品久久|
91久久福利国产成人精品|
国产精品久久久久免费a∨|
四虎国产永久免费久久|
久久夜色精品国产亚洲|
国产精品欧美久久久久无广告|
亚洲成色WWW久久网站|
久久综合久久鬼色|
久久九九青青国产精品|
热re99久久精品国99热|
国产69精品久久久久APP下载
|
午夜精品久久影院蜜桃
|
91精品日韩人妻无码久久不卡|
亚洲欧美久久久久9999|
精品午夜久久福利大片|
亚洲va中文字幕无码久久|
欧美精品国产综合久久|
女同久久|
污污内射久久一区二区欧美日韩|
91精品国产综合久久四虎久久无码一级|
亚洲愉拍99热成人精品热久久|
香蕉久久永久视频|
久久综合亚洲色HEZYO国产|
国产精品久久久久久久午夜片|
久久精品国产亚洲AV高清热
|
国产激情久久久久久熟女老人|
久久青青草原精品国产不卡|
久久精品国产WWW456C0M|
久久夜色撩人精品国产|
久久综合久久鬼色|
青青草原综合久久大伊人|
亚洲va中文字幕无码久久不卡|