貪心算法求單元最短路徑.doc

《貪心算法求單元最短路徑.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、#include"stdio.h"#include#include#includeusingnamespacestd;constintN=5;constintM=1000;ifstreamfin("4d5.txt");templatevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]);voidTraceback(intv,inti,intprev[]);//輸出最短路徑v源點，i終點intmain(){intv=1;//源點為1

2、intdist[N+1],prev[N+1],c[N+1][N+1];cout<<"有向圖權(quán)的矩陣為："<>c[i][j];cout<

3、atevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]){bools[N+1];for(inti=1;i<=n;i++){dist[i]=c[v][i];//dist[i]表示當(dāng)前從源到頂點i的最短特殊路徑長度s[i]=false;if(dist[i]==M){prev[i]=0;//記錄從源到頂點i的最短路徑i的前一個頂點}else{prev[i]=v;}}dist[v]=0;s[v]=true;for(inti=1;i

4、點//取出V-S中具有最短特殊路徑長度的頂點ufor(intj=1;j<=n;j++){if((!s[j])&&(dist[j]

5、prev[]){if(v==i){cout<"<