动态规划求最短路径代码,C代码库,德仔网

代码语言

代码分类

【C】动态规划求最短路径

作者:jpday / 发布于2013/10/23/ 669

Floyed算法动态规划求最短路径值并输出路径的走向。


	#include<iostream>
	#include<fstream>//文件读入读出判断的头文件
	#include<cstdlib>//exit(1)判断的头文件
	#include<cstdio>//freopen函数的头文件
	using namespace std;
	int main()
	{
	 int d[4][4],i,j,k,path[4][4],p1,p2,p[5000],t,t1;

	 {
	 t1=0;
	 ifstream infile("f1.txt");//freopen("f1.txt","r",stdin);
	 if(!infile)
	 {
	 cerr<<"open error!"<<endl;
	 exit(1);
	 }
	 for(i=0;i<4;i++)
	 {
	 for(j=0;j<4;j++)
	 {
	 infile>>d[i][j];
	 cout<<d[i][j]<<' ';
	 }
	 cout<<endl;
	 }
	 for(i=0;i<4;i++)
	 for(j=0;j<4;j++)
	 infile>>path[i][j];
	 for(k=0;k<4;k++)
	 for(i=0;i<4;i++)
	 for(j=0;j<4;j++)
	 {
	 if(d[i][j]>(d[i][k]+d[k][j]))
	 {
	 d[i][j]=d[i][k]+d[k][j];
	 path[i][j]=k;
	 }
	 }
	 for(i=0;i<4;i++)
	 {
	 for(j=0;j<4;j++)
	 cout<<d[i][j]<<' ';
	 cout<<endl;
	 }
	 for(i=0;i<4;i++)
	 {
	 for(j=0;j<4;j++)
	 cout<<path[i][j]<<' ';
	 cout<<endl;
	 }
	 infile.close();//注意要把文件结束后才可以在从键盘上输入
	 while(cin>>p1>>p2)
	 {
	 cout<<"The least short road ia "<<d[p1][p2]<<endl;
	 t=p2;
	 if(path[p1][p2]!=p1)
	 {
	 t1=1;
	 for(i=0;path[p1][p2]!=p1;i++)
	 {
	 p[i]=path[p1][p2];
	 p2=path[p1][p2];
	 }
	 }
	 cout<<"The road display is ";
	 cout<<p1<<"->";
	 if(t1)for(j=i-1;j>=0;j--)
	 cout<<p[j]<<"->";
	 cout<<t;
	 cout<<endl;
	 }
	 }
	 return 0;
	}

试试其它关键字

　Floyed　

同语言下

可能有用的

jpday贡献的其它代码(1)

.动态规划求最短路径