作者：未知 来源：月光软件站 加入时间：2005-5-13　月光软件站

source file:

#include <iostream.h>
#define M  100
#define n  7              //定义成7是为了看起来方便，这样就可以用a[6]来表示第六个点

int min(int a,int b)
{
 int c;
 if(a>b) c=b;
 else c=a;
 return c;
}

void main()
{
 int i,j,k;
 //initial(N);
 int N[n];
 N[1]=1;       //等于1就表示节点1在集合N中；N[i]＝1表示i点在集合N中
 //initial(L);
 int L[n][n]={           //节点距离矩阵
 {0            },
 {0,0,2,5,1,M,M},        //节点1
 {0,2,0,3,2,M,M},
 {0,5,3,0,3,1,5},
 {0,1,2,3,0,1,4},        //节点4
 {0,M,M,1,1,0,2},
 {0,M,M,5,4,2,0}
 };                    //节点距离矩阵输入结束
 //initial[S]
 int S[n][n];
 for(i=2;i<n;i++)
 {
  S[1][i]=L[1][i];   
 }
 for(j=2;j<n;j++)
 {
   N[j]=1;           //如果点不在N中，就加入到N中
   for(k=2;k<n;k++)  //修改不在N中的节点的S值
   {
    if(N[k]==1)
     S[j][k]=S[j-1][k];
    else
     S[j][k]=min(S[j-1][k],S[j-1][j]+L[j][k]);
   }
 }
 for(i=1;i<7;i++)
 {
  for(j=2;j<7;j++)
   cout<<S[i][j]<<",";
  cout<<endl;
 }
}

相关软件：