shortpaths.h

单源最短路径问题

#ifndef ShortPaths_
#define ShortPaths_
#include<iostream.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 T[n+1];
	for(int i=0;i<=n;i++)
	{
		dist[i]=-1;
		prev[i]=0;
	}
}

template<class T>
Graph<T>::~Graph()
{
	delete []dist;
	delete []prev;
}

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=j+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=v;
	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);
	}
}
#endif