int findmin(int disk[],bool S[],MGraph<T>M)
{
int k=0,min=MAX;
for(int i=0;i<M.vNum;i++)
{
if(!S[i]&&min>disk[i])
{
min=disk[i];
k=i;
}
}
if(min==MAX)return -1;
return k;
}
template<class T>
void print(int disk[],int P[],MGraph<T>M,T a[])
{
for(int i=0;i<M.vNum;i++)
{
cout<<a[i]<<"："<<disk[i]<<" {"<<a[i];
int pre=P[i];
while(pre!=-1)
{
cout<<a[pre];
pre=P[pre];
}
cout<<"}"<<endl;
}
}
template <class T >
void MGraph<T>::SP(MGraph<T>M,int v,int disk[],int P[],T a[])
{
int i;
bool S[MAX]={false};
for(i=0;i<M.vNum;i++)
{
disk[i]=M.arc[v][i];
if(disk[i]!=MAX)
P[i]=i;
else
P[i]=0;
}
S[v]=true;
disk[v]=0;
for(i=0;i<M.vNum;i++)
{
if((v=findmin(disk,S,M))==-1)
return ;
S[v]=true;
for(int j=0;j<M.vNum;j++)
if(!S[j]&&(disk[j]>M.arc[v][j]+disk[v]))
{
disk[j]=M.arc[v][j]+disk[v];
P[j]=v;
}
}
print(disk,P,M,a);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/87299.html
標籤：基礎類