floyd演算法c
#include<stdio.h>
#defineMAXNODE108
intpath[MAXNODE+1][MAXNODE+1]={0};
intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;
fpr=fopen("in.txt","r");/*讀取的文件名稱in.txt*/
fpw=fopen("out.txt","w");/*path的數據在out.txt中展現*/
while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;
for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;
if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw," ");
}
return0;
}
注意：floyd演算法中k為最外層，這是動態規劃的思想，不能改變i,j,k的順序！！！
這是之前的答案的錯誤之處。
-1表示不通。
具體程序分析，我可以加你QQ，願意的話，你把QQ寫給我。
② 數據結構C語言版Floyd演算法
您的理解不太對啊，每個矩陣D中記錄的都是頂點i到頂點j的當前所經頂點狀態下的最短路徑
③ C語言編程floyd法求助
for(i=0;i<n;i++){//輸出每對頂點間最短路徑長度及最短路徑
for(j=0;j<n;j++){
printf("%d到%d的最短長度:",i+1,j+1);
printf("%d\t",D[i][j]);//輸出Vi到Vj的最短路徑長度
printf("\n");
}
}
修改這里的就好了。不要全部輸出。
你可以定義一個變數 來累加 D[I][J]初步想法
int minzise = 0;
for(i=0;i<n;i++){//輸出每對頂點間最短路徑長度及最短路徑
for(j=0;j<n;j++){
minzise+= D[i][j];//
}
}
printf(「%d」),minzise)//符合你要求嗎？
④ floyd演算法 最短路徑 C語言
void Floyd(int **arr,int Vertex)
{
int i,j,k;
for(k=0;k<Vertex;k++)
for(i=0;i<Vertex;i++)
for(j=0;j<Vertex;j++)
{
if (arr[i][j]>arr[i][k]+arr[k][j])
{
arr[i][j] = arr[i][k]+arr[k][j];
}
}
}
⑤ floyd演算法中輸出最短路徑序列的C語言代碼
floyd是動態規劃的簡化,所以輸出路徑一樣套用dp的典型記錄方式即可.
即,每次鬆弛時,記錄是鬆弛了哪一個點.然後輸出時遞歸輸出即可.
弄一個矩陣R[][]初始化為0,然後比如你的距離矩陣是D[][]
鬆弛改為是:
if(D[i][j] > D[i][k]+D[k][j]){
D[i][j] = D[i][k]+D[k][j];
R[i][j] = k;
}
輸出時可以寫一個遞歸函數
function out(a,b){
if(R[a][b] == 0){
return;
}
out(a,R[a][b]);
//輸出k
out(R[a][b],b);
}
⑥ C語言最短路徑演算法問題，Floyd演算法行不通
要用演算法你也要先理解了再用啊，不懂你是修改了什麼，反正floyd肯定不是你這么寫，floyd要把中間結點的遍歷放在最三重循環的最外層。另外，求最短路徑是怎麼走的完全可以在更新最短路徑長度的過程中記錄中間結點是什麼，這並非演算法不能解決，而在於使用演算法的人是否真正懂得演算法過程，以及待解決的問題是否需要求解這方面的問題。
⑦ 求floyd最短路徑演算法，c語言代碼；
就是一個三重循環，核心代碼就這幾行
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
⑧ C++ 弗洛伊德演算法
#include<cstdio>
#include<cstdlib>
using namespace std;
int map[105][105];
int main()
{
int m,n,i,j,k,x,y,a,b,t;
scanf("%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=999999999;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&t);
map[x][y]=t;
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
}
}
}
scanf("%d%d",&a,&b);
printf("%d ",map[a][b]);
system("pause");
return 0;
}
第8行的scanf("%d",&n,&m);這里是不是寫錯了？
⑨ floyd演算法的c程序代碼
#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin("APSP.in");
ofstream fout("APSP.out");
int p,q,k,m;
int Vertex,Line[Maxm];
int Path[Maxm][Maxm],Map[Maxm][Maxm],Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p,Path[p][q]);
Root(Path[p][q],q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
for(p=1;p<=Vertex;p++)
if (Dist[p][k]>0)
for(q=1;q<=Vertex;q++)
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}
⑩ 如何利用弗洛伊德演算法求多源最短路徑問題c語言
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(f[i][j]>f[i][k]+f[k][j])
f[i][j]=f[i][k]+f[k][j];