#include<iostream.h>
void main()
{
int infinity=100, j, i, n, k, t, **w, *s, *p, *d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;
d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;1<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for (j=0;j<n;j++)
cin>>w[i][j];
for (s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if (d[i]<infinity) p[i]=0;
else p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for (j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j ;}
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
本内容试读结束,登录后可阅读更多
下载后可阅读完整内容,剩余2页未读,立即下载