1.问题描述：设G=(V,E)是一个有N个结点的有向图。又设C是G是成本邻接矩阵，其中C(i,i)=0,1<=i<=n;当<i,j>属于E(G)时，C(i,j)表示边<i,j>的成本；当i不等于j且<i,j>不属于E(G)时，C(i,j)等于无穷（用一个较大的数表示）。求出每对结点之间的最短路径。 2.设计思想与分析：
基本思路：首先决策哪个结点是该路径上的具有最大编号的中间结点K，然后就再去求取由I到K和由K到J这对结点间的最短路径，再把中间结点K记录下来。若是结点I，J间不用经过其他结点就能得到最短路径则把本身的成本保留下来，且不记录中间结点。 （本设计的遍历有问题，不能遍历经过2个结点的路径，一直没有修改。） #include <iostream.h>
int const m=4; struct node
{
int flag[m]; //用来记录每对结点最短路径要经过的结点
float cost; //用来记录结点到结点的路径成本
}; void all_paths(node COST[m][m],node A[m][m],int n)
{
int i,j,k;
//复制带路径成本的邻接矩阵
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
A[i][j].cost=COST[i][j].cost;
for(k=0;k<n;k++)
A[i][j].flag[k]=0;
} //*运用动态规划的的部分，核心算法*//
for(k=0;k<n;k++)//对最高下标为K的结点的路径
{
for(i=0;i<n;i++) //对于所有可能结点对
for(j=0;j<n;j++)
{
if(A[i][j].cost>(A[i][k].cost+A[k][j].cost))
{
A[i][j].cost=(A[i][k].cost+A[k][j].cost);
A[i][j].flag[k]=k+1; //记录要经过的结点编号
}
else A[i][j].cost=A[i][j].cost;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i!=j)
{ if(A[i][j].cost==100)
cout<<i+1<<"号结点无法到达"<<j+1<<"号结点"<<endl;
else
{
cout<<i+1<<"号结点到"<<j+1<<"号结点的最小路径成本为:"<<A[i][j].cost<<endl;
cout<<"其路径为:"<<i+1<<"->";
for(k=0;k<n;k++)
{
if(A[i][j].flag[k]!=0)
cout<<A[i][j].flag[k]<<"->";
}
cout<<j+1<<endl<<endl;
}
}
else cout<<endl;
}
}
} void main()
{ cout<<"|--------每对结点之间的最短路径-------|"<<endl;
cout<<"|---ower by zhanjiantao(028054115)---|"<<endl;
cout<<"|-------------------------------------|"<<endl<<endl;
cout<<"注意:请不要输入大于100的成本,本身到本身输入0，输入100表示无法到达"<<endl;
int i,j,n,k;
struct node COST[m][m];
struct node A[m][m];
while(k)
{
cout<<"结点总数为三个，请你构造这个图。"<<endl<<endl;
//cin>>n;
n=3;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
cout<<"请输入"<<i+1<<"号结点到第"<<j+1<<"号结点的路径成本:";
cin>>COST[i][j].cost;
}; all_paths(COST,A,n);
cout<<"Press<1> to run again"<<endl;
cout<<"Press<0> to exit"<<endl;
cin>>k;
}
}
|
本类阅读TOP10