本題的背景是求定點(diǎn)和定點(diǎn)之間的最短路問題（所有的最短路 不是一個(gè)解? 是全部解，方法手段來自數(shù)據(jù)結(jié)構(gòu)課程中的迪杰斯特拉算法和dfs（深度優(yōu)先遍歷）。

分別用兩種方法編程如下代碼

• dfs

#include <iostream> #include <cstring> #include <cstdio> using namespace std; #define maxv 510 bool visit[maxv];int arc[maxv][maxv];//鄰接矩陣int M,N,C1,C2; //M總頂點(diǎn)數(shù)，N總邊數(shù)，C1起點(diǎn)，C2終點(diǎn)int vex[maxv]; //記錄每個(gè)頂點(diǎn)的救援人數(shù)int mind=0xfffffff,maxr=0,cnt;//mind最短路徑，maxr最大救援人數(shù)，cnt最短路徑條數(shù)void dfs(int st,int end,int curPath,int curRes){if (st==end){if (curPath<mind){cnt=1;mind=curPath;maxr=curRes;}else if(curPath==mind){cnt++;if (curRes>maxr)maxr=curRes;}return;}else{for (int k=0;k<M;k++){if (arc[st][k]!=0&&!visit[k]){visit[k]=1;dfs(k,end,curPath+arc[st][k],curRes+vex[k]);visit[k]=0;}}return ;} } int main(){while(scanf("%d%d%d%d",&M,&N,&C1,&C2)!=EOF){memset(arc,0,sizeof(arc));for(int i=0;i<M;i++)scanf("%d",&vex[i]);int i,j,d;for(int k=0;k<N;k++){scanf("%d%d%d",&i,&j,&d);arc[j][i]=arc[i][j]=d;}memset(visit,0,sizeof(visit));visit[C1]=1;dfs(C1,C2,0,vex[C1]);printf("%d %d",cnt,maxr);}return 0; }

容易放的錯(cuò)誤是mind,maxr忘記賦初始值? ??

矩陣scanf輸入的時(shí)候&arg[i][j]? 不會(huì)報(bào)錯(cuò)? 但會(huì)導(dǎo)致輸入異常? ?這個(gè)問題我也很奇怪? 先在這里記錄說明了

?

• 　　迪杰斯特拉算法

#include <iostream> #include <cstdio> using namespace std; #define maxv 510 #define inf 65536int arc[maxv][maxv];//鄰接矩陣int M,N,C1,C2; //M總頂點(diǎn)數(shù)，N總邊數(shù)，C1起點(diǎn)，C2終點(diǎn)int vex[maxv]; //記錄每個(gè)頂點(diǎn)的救援人數(shù)int maxr=0,cnt;//mind最短路徑，maxr最大救援人數(shù)，cnt最短路徑條數(shù)int Path[maxv],D[maxv],S[maxv];//Path[]記錄從源點(diǎn)v0到終點(diǎn)vi的直接前驅(qū)頂點(diǎn)序號(hào)//D[]記錄從源點(diǎn)v0到終點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度//S[]記錄從源點(diǎn)v0到源點(diǎn)vi是否已經(jīng)被確定最短路徑長(zhǎng)度/*計(jì)算v0到j(luò)的當(dāng)前最大救援人數(shù)*/ void compute(int v0,int j){int curRes=vex[v0];for (int k=j;k!=v0;k=Path[k]){curRes+=vex[k];}if (curRes>maxr)maxr=curRes;return; }void dijistra(int v0,int v){int mind,w;//mind最短路徑 w被加入到S中的頂點(diǎn)序號(hào)int curRes=0;/*初始化*/for (int i=0;i<M;i++){S[i]=false;D[i]=arc[v0][i];if (D[i]<inf)Path[i]=v0;elsePath[i]=-1;}cnt=1;compute(v0,v);S[v0]=true;D[v0]=0;/*v0到其他M-1個(gè)頂點(diǎn)的最短路徑*/for (int i=1;i<M;i++){mind=inf;for (int j=0;j<M;j++)if (!S[j]&&D[j]<mind){w=j;mind=D[j];}S[w]=true;for (int j=0;j<M;j++)if (!S[j]&&(D[w]+arc[w][j]<D[j])){D[j]=D[w]+arc[w][j];Path[j]=w;if (j==v){cnt=1;maxr=0;compute(v0,j);}}else if (!S[j]&&D[w]+arc[w][j]==D[j]){Path[j]=w;if (j==v){cnt++;/*v0到頂點(diǎn)j的當(dāng)前最短路徑不止一條*/compute(v0,j);}}}return; } int main(){while(scanf("%d%d%d%d",&M,&N,&C1,&C2)!=EOF){for (int i=0;i<M;i++)for (int j=0;j<M;j++)arc[i][j]=inf;for(int i=0;i<M;i++)scanf("%d",&vex[i]);int i,j,d;for(int k=0;k<N;k++){scanf("%d%d%d",&i,&j,&d);arc[j][i]=arc[i][j]=d;}dijistra(C1,C2);printf("%d %d\n",cnt,maxr);//printf("%d %d %d %d %d\n",cnt,maxr,D[C2],Path[C2],Path[Path[C2]]);/*for (int i=0;i<M;i++){for (int j=0;j<M;j++)printf("%d ",arc[i][j]);printf("\n");}*/}return 0; }

　　這段代碼目前只能通過pat平臺(tái)的三個(gè)測(cè)試樣例? 得 16分? ?后續(xù)會(huì) 改bug??

轉(zhuǎn)載于:https://www.cnblogs.com/mdz-great-world/p/7598108.html

總結(jié)

以上是生活随笔為你收集整理的pat1003 迪杰斯特拉法和dfs求最短路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。