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