 #include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
//引以为荣的程序.还有几个小部分改,以待完美.
const int N=7,MAX=1000;
  class PrimTree {
 int map[N][N];
bool beVisited[N];
bool beExist[N];
int count;
int Pass[N];
public:
PrimTree(int table[][N]);//构建 Prim树
int Go(int startnode,int endnode,int *& info,int & len);//从结点startnode到endnode,返回最短路径及详细信息
int DFS(int v,int endonde);//从第v个顶点出发深度遍历map
 };
PrimTree::PrimTree(int table[][N])
{
  bool beInclude[N]={false};
int lowcost[N]={0};
int startnode[N]={0};
for (int i=2;i<=N;i++)
{
lowcost[i]=table[1][i]; //lowcost初始化为从第一个结点到各个节点的距离
startnode[i]=1; //起始结点
 }
startnode[1]=1;
beInclude[1]=true; //结节1被包含进入目标图中
for (int m=0;m<N-1;m++)
{
int temp=MAX,armRow=0;
for (int x=2;x<=N;x++)
{
if (lowcost[x]<temp && !beInclude[x])
{
temp=lowcost[x]; armRow=x;
}
}
beInclude[armRow]=true;
//更新划入范围的结点到其它结点的最短距离
for(int y=1;y<=N;y++)
{
if (table[armRow][y]<lowcost[y] && !beInclude[y])
{
lowcost[y]=table[armRow][y];
startnode[y]=armRow;
}
}
}
/**//*
for test.
copy(lowcost+1,lowcost+N,ostream_iterator<int>(cout," "));
cout<<endl;
copy(startnode+1,startnode+N,ostream_iterator<int>(cout," "));
cout<<endl;
*/
//建立Prim树的矩阵图.
{
for (int i=0;i<N;i++)
{
for (int j=0;j<N;j++)
{
map[i][j]=0;
}
}
}
{
for (int i=2;i<N;i++)
{
map[startnode[i]][i]=lowcost[i];
map[i][startnode[i]]=lowcost[i];
}
}
}
int PrimTree::Go(int startnode,int endnode,int * &info,int &len)
{
//出始化成员变量
for (int i=1;i<=N-1;i++)
{
beExist[i]=true;
beVisited[i]=false;
Pass[i]=0;
}
count=0;
DFS(startnode,endnode);
/**//*
for test.
copy(beVisited+1,beVisited+N,ostream_iterator<bool>(cout," "));
cout<<endl;
copy(beExist+1,beExist+N,ostream_iterator<bool>(cout," "));
cout<<endl;
copy(Pass,Pass+N,ostream_iterator<int>(cout," "));
cout<<endl;
*/
//找出从起始到终止结点间的途径节点
vector<int> col;
{
for (int i=0;i<N;i++)
{
if (Pass[i] && beExist[Pass[i]])
{
col.push_back(Pass[i]);
//cout<<Pass[i]<<"->";
}
}
}
info=new int[col.size()];
copy(col.begin(),col.end(),info);
len=col.size();
/**//*
for test
copy(info,info+col.size(),ostream_iterator<int>(cout," "));
cout<<endl;
*/
int lou=0;
//计算起点到终点的具体长度.
{
int b=0,n=1;
for (int i=0;i<col.size()-1;i++)
{
lou+=map[info[b]][info[n]];
b=n;
n++;
}
//cout<<lou<<endl;
}
return lou;
}
// It works! Great! 终于写好了这个最短路径的算法,
// 先遍历图,再标出旁路的节点..great!!!! zhangyuntao 3.31 原创经典.
int PrimTree::DFS(int v,int endonde)
{
Pass[count++]=v;
beVisited[v]=true;
if(v==endonde) return 1;
int m=0;
for (int i=1;i<=N-1;i++)
{
if (map[v][i] && !beVisited[i])
{
m+=DFS(i,endonde);
}
}
if (m==0)
{
beExist[v]=false; //歧路标志设为0;
return 0;
}
return 1;
}
//Great!
void main()
{
int table[N][N]={
{MAX,MAX,MAX,MAX,MAX,MAX,MAX},
{MAX,MAX,6, 1, 5, MAX,MAX},
{MAX,6, MAX,5, MAX,3, MAX},
{MAX,1, 5, MAX,5, 6, 4},
{MAX,5, MAX,5, MAX,MAX,2},
{MAX,MAX,3, 6, MAX,MAX,1},
{MAX,MAX,MAX,4, 2, 1, MAX},
};
{
for (int i=1;i<N;i++)
{
for (int j=1;j<N;j++)
{
cout<<setw(5)<<(table[i][j]== MAX ? -1 : table[i][j]);
}
cout<<endl;
}
}
cout<<"--------------------------------------------------"<<endl;
PrimTree p(table);
int start,end;
cout<<"输入起始节点与终止节点(1到6)"<<endl;
int *info ,len;
while(cin>>start>>end)
{
if (start<=6 && end<=6)
{
cout<<"最短路径为 "<<p.Go(start,end,info,len)<<endl;
copy(info,info+len-1,ostream_iterator<int>(cout,"->"));
cout<<info[len-1]<<endl;
delete []info;
}
cout<<"输入起始节点与终止节点"<<endl;
}
system("pause") ;
}
|