#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define maxn 1005 int D[maxn][maxn]; int P[maxn][maxn]; int N,M; //頂點數(shù)邊數(shù) int S,E; //起點終點 void Floyd() {for(int k=1;k<=N;k++)for(int i=1;i<=N;i++)for(int j=1;j<=N;j++){if(D[i][j]>D[i][k]+D[k][j]){D[i][j]=D[i][k]+D[k][j];P[i][j]=P[k][j];}} } int main() {//initmemset(D,0x3f,sizeof(D));memset(P,0x3f,sizeof(P));//錄入圖cin>>N>>M;for(int i=1;i<=M;i++){int u,v,cost;cin>>u>>v>>cost;if(cost<D[u][v]) //D的初始化為邊的信息{D[u][v]=cost;//D[v][u]=cost;//無向圖}}for(int i=1;i<=N;i++) //初始化Pfor(int j=1;j<=N;j++){if(i!=j&&D[i][j]!=INF) //P第0層為iP[i][j]=i;}cin>>S>>E;//Floyd();//最短距離cout<<D[S][E]<<endl;//路徑回溯int temp=P[S][E];cout<<E;while(true){if(temp==S){cout<<"<--"<<S<<endl;break;}cout<<"<-"<<P[S][temp];temp=P[S][temp];} }

?

總結(jié)

以上是生活随笔為你收集整理的图论--最短路--Floyd（含路径输出）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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