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; }}
|
[【技术文档】]算法连载（5）--动态规划之allPath[转载]