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

            常用鏈接

            統(tǒng)計

            最新評論

            每對頂點間的最短路徑之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 原語餓狼 閱讀(362) 評論(0)  編輯 收藏 引用 所屬分類: 圖論

            久久乐国产综合亚洲精品| 亚洲综合久久综合激情久久| AV色综合久久天堂AV色综合在| 久久久中文字幕| 免费精品久久天干天干| 久久成人精品视频| 精品无码久久久久国产动漫3d| 国产69精品久久久久99| 69SEX久久精品国产麻豆| 久久电影网| 99久久无码一区人妻a黑| 久久久久久久精品妇女99| 久久强奷乱码老熟女| 欧美久久精品一级c片片| 久久精品国产亚洲AV嫖农村妇女| 污污内射久久一区二区欧美日韩| 99久久精品九九亚洲精品| 国内精品久久国产大陆| 欧美一区二区三区久久综| 色婷婷久久久SWAG精品| 久久国产精品免费一区| 国产福利电影一区二区三区久久久久成人精品综合| 久久精品卫校国产小美女| 三级韩国一区久久二区综合| 欧美一级久久久久久久大片| 99久久综合国产精品二区| 91精品国产91久久久久久| 色综合久久中文色婷婷| 99精品久久久久久久婷婷| 国产 亚洲 欧美 另类 久久| 久久精品视屏| 亚洲午夜久久久久久噜噜噜| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久国产精品久久精品国产| 久久久精品人妻一区二区三区蜜桃 | 久久精品人妻一区二区三区| 久久国产精品国语对白| 久久久WWW成人| 久久香综合精品久久伊人| 久久精品国产亚洲av麻豆图片 | 亚洲精品视频久久久|