分支优先队列解单源最短路径.cpp

算法分析中

#include<iostream>
#include "tree.h"
#include "binheap.h"
#include <algorithm>
#include <deque>
using namespace std;

template<class Type>
class Graph
{
	friend int main();
	public:
		void ShortestPaths(int);
	private:
		int n;
		//图G的顶点数
		int *prev;
		//前趋顶点数组
		Type **c;
		//图G的邻接矩阵
		Type *dist;
		//最短距离数组
};

template<class Type>
class MinHeapNode
{
	friend Graph<Type>;
	public:
		MinHeapNode()
		{
		};

		MinHeapNode( MinHeapNode& a )
		{
			i = a.i;
			length = a.length;
		};

		operator int() const
		{
			return length;
		};

		bool operator >( MinHeapNode& a ) const
		{
			return length > a.length;
		};

		bool operator <( MinHeapNode& a ) const
		{
			return length < a.length;
		};

	private:
		int i;
		//顶点编号
		Type length;
		//当前路长
};

/*
堆结构：
堆就是一棵完全二叉树
数组来存储各个结点
数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在2*i+1上，当然了存储下标从1开始

堆序性质
在一个堆中，对于每一个结点x，x的父亲中的关键字小于x中的关键字，根结点除外
*/
const int max = 100;
template<class Type>
class MinHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MinHeap(int n)
		{
			H = NULL;
			H = (Type*)malloc( sizeof( Type ) * ( n + 1 ) );
			Capacity = n;
			Size = 0;
		};
		MinHeap( MinHeap& a )
		{
			//要排除自赋值的情况
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		}

		/*
		基本的堆插入操作
		为了将node插入到堆中
		首先在下一个空闲位置++Size处，创建一个空穴，否则该堆将不是完全树
		如果x可以放在该穴中而不破坏堆的序，那么插入完成
		否则我们把空穴的父亲结点上的元素移动到该穴中，这样空穴就朝着根的方向上行一步
		继续该过程直到x能被放入空穴为止
		*/
		Insert( Type& node )
		{
			for( int i = ++Size; H[ i / 2 ] > node; i /= 2 )
			{
				H[i] = H[ i / 2 ];
			}
			H[i] = node;
			cout<<"Size = "<<Size<<endl;
		};

		/*
		当删除一个最小元时
		在根结点处产生一个空穴。
		由于现在堆少了一个元素，因此堆中最后一个元素必须移动到该堆的某个地方
		如果x可以放到空穴中，那么DeleteMin完成
		否则应该将两个儿子中较小者移入空穴
		这样空穴就向下推了一层。重复该步骤直到x可以被放入空穴中
		*/
		DeleteMin( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			MinElement = H[ 1 ];
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] < H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement > H[ Child ] )
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			H[ i ] = LastElement;
			node = MinElement;

		};
};
/*
掌握如何实现优先队列，利用二叉堆，孩子结点都大于父亲结点
*/

template<class Type>
void Graph<Type>::ShortestPaths(int v)
{
	//单源最短路径问题的优先队列式分支界限法
	//定义最小堆的容量为1000
	MinHeap< MinHeapNode<Type> > H(10);
	//deque< MinHeapNode<Type> > H(1000);
	 
	MinHeapNode<Type> E;
	
	E.i = v;
	E.length = 0;
	dist[v] = 0;
	//搜索问题的解空间
	while(true)
	{
		for( int j = 1; j <= n; ++j )
		{
			
			if ( ( c[E.i][j] < 1000) && ( E.length + c[E.i][j] < dist[j] ) )
				//顶点i到顶点j可达,且满足控制约束
			{
				dist[j] = E.length + c[E.i][j];
				prev[j] = E.i;
				//加入到活结点优先队列
				//此时j有可能是单源最短路径上要经过的点，所以加入
				
				MinHeapNode<Type> N;
				N.i = j;
				N.length = dist[j];
				cout<<"j = "<<j<<endl;
				cout<<"N.i = "<<N.i<<endl;
				cout<<"N.length = "<<N.length<<endl;
				
				H.Insert(N);
			}	
			
		}
		if ( H.Size == 0 )
		{
			cout<<dist[1]<<" "<<dist[2]<<" "<<dist[3]<<" "<<dist[4]<<endl;
			break;
		}
		else
		{
			H.DeleteMin(E);
		}
		
	//getchar();
	}
}    
 
int main()
{
	Graph<int> gra;
	
	gra.c = new int*[5];
	for(int i = 0; i < 5; ++i )
	{
		gra.c[i] = new int[5];
	}
	
	gra.c[1][1] = 0;
	gra.c[1][2] = 2;
	gra.c[1][3] = 1;
	gra.c[1][4] = 1000;
	gra.c[2][1] = 1000;
	gra.c[2][2] = 0;
	gra.c[2][3] = 1000;
	gra.c[2][4] = 3;
	gra.c[3][1] = 1000;
	gra.c[3][2] = 1000;
	gra.c[3][3] = 0;
	gra.c[3][4] = 5;
	gra.c[4][1] = 1000;
	gra.c[4][2] = 1000;
	gra.c[4][3] = 1000;
	gra.c[4][4] = 0;

	gra.n = 4;
	gra.dist = new int[5];
	gra.prev = new int[5];
	for( i = 0; i < 5; ++i )
	{
		gra.dist[i] = 1000;
		gra.prev[i] = 0;
	}

	gra.ShortestPaths(1);
	return 0;
}