青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

yuanyuelang

常用鏈接

統計

最新評論

單源最短路徑之Dijkstra算法


單源最短路徑,解決的是什么問題呢?
顧名思義,單源說明從一個源出發,出發到哪里呢?不管到哪里我都要求得一個最短的路徑。

比較正式的說法:
對于有向圖G={V,E},帶權,注意Dijkstra算法要求所有的權值非負,
假設我們的源是s,源點要到達的點集合是S,我們每次選擇具有最短路徑估計的頂點u(u在V-S中,并將u加入到S中,然后此時要對u所有的出邊進行處理,怎么處理,我們要最短路徑,所以此時要判斷s經過u到達V-S中的點會不會比不經過u到達來的小,更新呵呵..

那么怎么寫成代碼呢?
1.我們需要二維數組graph[][]表示圖,用distance[]數組來表示源點V0到其它頂點的最短路徑distance[v],我們還要保存具體路徑,我們用path[][]二維bool數組來表示,path[1]就表示源點到頂點V1的路徑,path[1][0,n-1]數組里面的元素如果為true表示V0有經過那些頂點到達V1
2.我們還要考慮到頂點是否已經加到S中,用一個flag數組來標志頂點是否已經求的最短路徑了。

還要分清是有向圖還是無向圖,這對于入邊和出邊在程序處理的時候要注意。 

#define MAXN 100
#define INF 0xfffffff


//注意graph里面的數據,兩頂點i指向j有邊,長為r,則graph[i][j]=r,其余情況graph為INF,包括i==j

void dijkstra(int graph[MAXN][MAXN],bool path[MAXN][MAXN],int distance[],int n)
{
    
int i,j,min,vertex;
    
bool flag[MAXN];
    
for(i=0;i<n;i++){//初始化
        distance[i]=graph[0][i];
        flag[i]
=false;
        
for(j=0;j<n;j++) path[i][j]=false;
        
if(distance[i]<INF)//路徑必定至少有v0和vi兩個頂點
            p[i][0]=true;p[i][i]=true;
        }

    }


    flag[
0]=true;
    distance[
0]=0;//注意一定要初始化distance[0]
    for(i=1;i<n;i++){
        min
=INF;
        
for(j=1;j<n;j++)
            
if(!flag[j]&&distance[j]<min){//找到最近的點
                min=distance[j];
                vertex
=j;
            }

        flag[vertex]
=true;
        
for(j=1;j<n;j++)
            
if(!flag[j]&&graph[vertex][j]+min<distance[j]){//如果可以通過vertex更近的話,更新
                distance[j]=graph[vertex][j]+min;
                
for(int k=0;k<n;k++) path[j][k]=path[vertex][k];
                path[j][j]
=true;
            }

    }


}


請讀者務必自己舉個例子,運行看看,這樣子才能理解好理解的根深蒂固,還有一定要自己不斷的寫,自己平常要鍛煉,做ACM題目時最好自己再寫一遍,不要太依賴模板了哈哈。。

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美精品少妇一区二区三区| 亚洲人成在线影院| 国产亚洲人成网站在线观看| 国产精品九九| 国产精品久久久久久久久久免费 | 欧美一区二区三区免费观看视频| 亚洲午夜三级在线| 在线亚洲伦理| 香蕉成人久久| 久久天天躁夜夜躁狠狠躁2022| 欧美77777| 亚洲激情黄色| 亚洲午夜久久久| 久久久99国产精品免费| 蜜臀a∨国产成人精品 | 影音先锋中文字幕一区| 亚洲高清色综合| 一区二区欧美在线| 久久三级福利| 99re热这里只有精品视频| 性做久久久久久免费观看欧美| 久久频这里精品99香蕉| 欧美巨乳在线| 国产色爱av资源综合区| 亚洲日韩中文字幕在线播放| 久久aⅴ乱码一区二区三区| 亚洲国产成人在线| 亚洲欧美日韩国产综合在线| 欧美另类女人| 伊人成人在线| 性欧美8khd高清极品| 欧美激情自拍| 欧美一区二区三区免费观看| 欧美日本精品| 亚洲国产综合在线| 欧美一区日韩一区| 亚洲美女av黄| 欧美激情在线播放| 亚洲高清二区| 噜噜噜躁狠狠躁狠狠精品视频| 一区二区三区免费看| 美脚丝袜一区二区三区在线观看| 国产乱人伦精品一区二区| 亚洲精品欧美精品| 免费日韩一区二区| 午夜精品www| 亚洲黄色免费电影| 久久国产精品99久久久久久老狼| 欧美日韩免费高清一区色橹橹| 在线观看视频免费一区二区三区| 欧美一区二区啪啪| 99精品国产热久久91蜜凸| 欧美国产欧美亚洲国产日韩mv天天看完整 | 欧美人体xx| 亚洲国产影院| 欧美二区在线| 久久午夜精品一区二区| 影音先锋中文字幕一区二区| 欧美在线视频一区二区三区| 亚洲在线视频一区| 国产精品乱码妇女bbbb| 亚洲欧美日韩综合一区| 99在线精品视频| 欧美日韩综合一区| 亚洲在线观看免费| 亚洲性视频h| 国产日韩欧美在线视频观看| 午夜一区二区三区不卡视频| 亚洲在线中文字幕| 国产日韩精品视频一区| 久久久国产一区二区三区| 欧美制服丝袜| 亚洲国产成人久久综合一区| 亚洲第一区中文99精品| 欧美精品一区二区三区视频 | 久久狠狠一本精品综合网| 亚洲欧美在线免费观看| 国产一区二区三区视频在线观看| 久久人人97超碰国产公开结果| 久久久91精品国产一区二区三区 | 欧美日韩卡一卡二| 亚洲伊人一本大道中文字幕| 午夜精品免费在线| 一区二区三区在线不卡| 欧美激情中文字幕在线| 欧美日韩中文字幕综合视频| 免费亚洲电影在线| 亚洲精品免费在线| 亚洲大片免费看| 欧美视频一区二| 久久久久国产一区二区三区| 老司机午夜精品视频| 一区二区三区毛片| 午夜一级久久| 99视频精品在线| 亚洲欧美日韩一区二区| 91久久久久| 亚久久调教视频| 日韩天堂在线观看| 久久精品国产精品| 在线视频亚洲一区| 午夜宅男欧美| 亚洲美女视频| 久久久精品免费视频| 亚洲一区欧美一区| 你懂的成人av| 久久久国际精品| 欧美视频一区二区三区四区 | 一本一本久久a久久精品综合妖精| 国产精品一区一区三区| 亚洲高清不卡在线观看| 国产丝袜一区二区三区| 亚洲美女毛片| 91久久夜色精品国产九色| 午夜精品在线看| 99在线观看免费视频精品观看| 欧美在线视频一区二区三区| 亚洲视频视频在线| 欧美激情按摩| 欧美国产精品久久| 韩国v欧美v日本v亚洲v| 亚洲视频在线观看| 中文国产成人精品| 欧美精品xxxxbbbb| 欧美大胆a视频| 伊人影院久久| 久久精品青青大伊人av| 久久精品国产欧美激情| 国产精品视区| 亚洲一级在线观看| 午夜日韩福利| 国产精品一卡二卡| 亚洲一区二区三区高清| 亚洲尤物在线| 国产精品久久久久aaaa樱花| 一本一本久久| 亚洲免费影院| 国产日韩成人精品| 欧美一区二区啪啪| 久久综合九色综合欧美狠狠| 好看的日韩av电影| 久久久久久久91| 美国十次成人| 亚洲第一福利视频| 麻豆精品91| 亚洲国产欧洲综合997久久| 亚洲区中文字幕| 欧美精品在线一区二区三区| 日韩视频三区| 午夜精品久久久久久久白皮肤 | 亚洲电影一级黄| 亚洲国产免费看| 欧美激情aⅴ一区二区三区| 日韩天天综合| 性欧美大战久久久久久久免费观看| 国产精品视频网站| 久久精品人人爽| 亚洲国产精品一区二区www在线| 亚洲靠逼com| 国产精品大全| 久久精品亚洲一区| 亚洲欧洲日本mm| 午夜精品视频在线观看| 禁久久精品乱码| 欧美日韩1234| 欧美在线观看www| 亚洲国产成人精品久久久国产成人一区| 欧美激情一区二区三区四区 | 国产日韩av在线播放| 久久久国产午夜精品| 久久久久久久精| 亚洲精品美女久久7777777| 欧美日韩在线一二三| 久久精品国产免费观看| 亚洲精品一区二区三区99| 久久成人综合视频| 亚洲日本成人在线观看| 国产精品家庭影院| 免费成人av在线| 午夜精品国产更新| 亚洲毛片一区| 欧美大胆a视频| 久久九九国产精品| 亚洲尤物精选| 亚洲美女视频| 在线不卡视频| 国产日韩欧美一二三区| 欧美日韩综合视频网址| 免费人成网站在线观看欧美高清| 亚洲免费影视| avtt综合网| 亚洲激情视频网站| 老鸭窝毛片一区二区三区| 亚洲欧美日韩另类| 日韩亚洲欧美在线观看| 亚洲福利视频在线| 国产婷婷色一区二区三区在线 | 欧美黄色小视频| 久久久久成人精品免费播放动漫| 亚洲在线一区二区|