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;
   }
}