shortpath.h

算法设计的分支限界法中的单源最短路径问题的实现

#include"MinHeap.h"
template<class T>class Graph;
template<class T>class MinHeapNode
{
	friend class Graph;
	public:
		operator int ()const
		{return length;}
	//private:
		int i;
		T length;
};
template<class T>class Graph
{
	public:
		Graph(int,T**,T);
		~Graph();
		void ShortPath(int);
		void print(int);
	private:
		int n,
			*prev;
		T **c,
			*dist,
			NoEdge;
};
template<class T>Graph<T>::Graph(int n1,T **c1,T NoEdge1)
{
	n=n1;
	c=c1;
	NoEdge=NoEdge1;
	prev=new int [n+1];
	dist=new int[n+1];
	for(int i=0;i<=n;i++)
	{
		dist[i]=-1;
		prev[i]=0;
	}
}
template<class T>Graph<T>::~Graph()
{
	delete [] prev;
	delete [] dist;
}
template<class T>void Graph<T>::print(int v1)
{
	int *bestx=new int[n+1],v=v1,j=n-1;
	bestx[n]=v;
	while(prev[v]!=0)
	{
		v=bestx[j--]=prev[v];
	}
	j++;
	cout<<"最优路径:"<<endl;
	cout<<bestx[j];
	for(int i=1;i<=n;i++)
		cout<<"->"<<bestx[i];
	cout<<endl;
	cout<<"最优值为:"<<dist[v1]<<endl;
	cout<<endl<<endl;
}
template<class T>void Graph<T>::ShortPath(int v)
{
	MinHeap<MinHeapNode<T> > H(100);
	MinHeapNode<T> E;
	E.i=0;
	E.length=0;
	dist[v]=0;
	prev[v]=0;
	while(true)
	{
		for(int j=1;j<=n;j++)
		{
			if((c[E.i][j]!=NoEdge)&&(E.length+c[E.i][j]<dist[j]
				||dist[j]==NoEdge))
			{
				dist[j]=E.length+c[E.i][j];
				prev[j]=E.i;
				MinHeapNode<T> N;
				N.i=j;
				N.length=dist[j];
				H.Insert(N);
		}}
		if(H.IsEmpty())
			break;
		H.DeleteMin(E);
	}
}