xdijkstra.h

最短路径的并行算法 采用TBB 需要intel编译器 速度很快

/*/////////////////////////////////////////
// 版权所有(C)  2000-2008 邓辉           //
// Email：      [e-mail]  //
// 说明：       Intel线程优化大赛参赛作品//
/////////////////////////////////////////*/

#ifndef XDIJKSTRA_HEAD
#define XDIJKSTRA_HEAD

#include "XShortestPub.h"

// 二叉堆 FixDown
template <class Type>
__inline void XFixDown(int i, int nHeap, XNode<Type>* pHeap, int* pTab)
{
	int j = i * 2 + 1;
	if (j + 1 < nHeap && pHeap[j + 1].xKey < pHeap[j].xKey) ++j;
	while (j < nHeap && pHeap[i].xKey > pHeap[j].xKey)
	{
		const XNode<Type> tmp = pHeap[i]; pHeap[i] = pHeap[j]; pHeap[j] = tmp;
		pTab[pHeap[i].nID] = i;
		pTab[pHeap[j].nID] = j;
		i = j; j = i * 2 + 1;
		if(j + 1 < nHeap && pHeap[j + 1].xKey < pHeap[j].xKey) ++j;
	}
}

// 二叉堆 FixUp
template <class Type>
__inline void XFixUp(int i, XNode<Type>* pHeap, int* pTab)
{	
	int j = (i - 1) >> 1;
	while(i > 0 && pHeap[i].xKey < pHeap[j].xKey)
	{
		const XNode<Type> tmp = pHeap[i]; pHeap[i] = pHeap[j]; pHeap[j] = tmp;
		pTab[pHeap[i].nID] = i;
		pTab[pHeap[j].nID] = j;
		i = j; j = (i - 1) >> 1;
	}
}

// Dijkstra算法
template <class Type>
void XDijkstraLine(XGraph<Type>* pGraph, int nBegin)
{
	int*			pTab  = (int*)scalable_malloc(pGraph->nNode * sizeof(pTab[0]));
	char*			pFlag = (char*)scalable_malloc(pGraph->nNode * sizeof(pFlag[0]));
	XNode<Type>*	pHeap = (XNode<Type>*)scalable_malloc(pGraph->nNode * sizeof(pHeap[0]));
	XEdge<Type>**	pHead = pGraph->pHead;
	Type*			pDistance = pGraph->ppDistance[nBegin];
	int				i,nHeap = 0, nNode = pGraph->nNode;

	memset(pTab,  -1, nNode * sizeof(pTab[0]));
	memset(pFlag, 1,  nNode * sizeof(pFlag[0]));
	 
	pHeap[0].xKey = pDistance[nBegin] = 0; 
	pHeap[0].nID  = nBegin;
	pTab[nBegin]  = 0;
	pFlag[nBegin] = 0;

	for(i = 0; i < nNode && pDistance[i] != XDISTANCE_INFINITY; ++i) pFlag[i] = 0;

	// 对已经得到最小距离的点,将与其相连接的点加入堆中
	for(i = 0; i < nNode; ++i)
	{
		if(pFlag[i] == 0)
		{
			for(XEdge<Type>* pCur = pHead[i]; pCur != NULL; pCur = pCur->pNext)
			{
				if(pFlag[pCur->nLink]) 
				{
					if(pTab[pCur->nLink] == -1)
					{	// 该点不在堆中
						pDistance[pCur->nLink] = pHeap[nHeap].xKey = pDistance[i] + pCur->xKey;
 						pHeap[nHeap].nID = pCur->nLink;
						pTab[pCur->nLink] = nHeap++;
						XFixUp(nHeap - 1, pHeap, pTab);
					}
					else if(pDistance[i] + pCur->xKey < pHeap[pTab[pCur->nLink]].xKey)
					{	// 该点在堆中
						pDistance[pCur->nLink] = pHeap[pTab[pCur->nLink]].xKey = pDistance[i] + pCur->xKey;
						XFixUp(pTab[pCur->nLink], pHeap, pTab);
					}
				}
			}
		}
	}
	
	while(nHeap > 0)
	{
		// 取出当前与已经确定的所有点的距离最小的点
		--nHeap;

		const Type xMinKey = pHeap[0].xKey;
		const int  nMinID  = pHeap[0].nID;
		
		const XNode<Type> tmp = pHeap[0]; pHeap[0] = pHeap[nHeap]; pHeap[nHeap] = tmp;
		pTab[pHeap[0].nID] = 0;
		pTab[nMinID] = nHeap;

		XFixDown(0, nHeap, pHeap, pTab);

		pFlag[nMinID] = 0;

		// 更新与该点连接的 所有点的最小距离
		for(XEdge<Type>* pCur = pHead[nMinID]; pCur != NULL; pCur = pCur->pNext)
		{
			if(pFlag[pCur->nLink]) 
			{
				if(pTab[pCur->nLink] == -1)
				{	// 该点不在堆中
					pDistance[pCur->nLink] = pHeap[nHeap].xKey = xMinKey + pCur->xKey;
					pHeap[nHeap].nID = pCur->nLink;
					pTab[pCur->nLink] = nHeap++;
					XFixUp(nHeap - 1, pHeap, pTab);
				}
				else if(xMinKey + pCur->xKey < pHeap[pTab[pCur->nLink]].xKey)
				{	// 该点在堆中
					pDistance[pCur->nLink] = pHeap[pTab[pCur->nLink]].xKey = xMinKey + pCur->xKey;
					XFixUp(pTab[pCur->nLink], pHeap, pTab);
				}
			}
		}
	}

	// 标记已经知道的最小距离
	Type** ppDistance = pGraph->ppDistance;
	for(i = nBegin + 1; i < nNode; ++i) ppDistance[i][nBegin] = pDistance[i];

	// 删除不是最小值的边
	XEdge<Type>  xCur;
	xCur.pNext = pHead[nBegin];
	for(XEdge<Type>* pCur = &xCur; pCur->pNext != NULL; )
	{
		if(pCur->pNext->xKey > pDistance[pCur->pNext->nLink]) 
		{
			pCur->pNext = pCur->pNext->pNext;
		}
		else
		{
			pCur = pCur->pNext;
		}
	}
	pHead[nBegin] = xCur.pNext;

	if(pTab != NULL) scalable_free(pTab);
	if(pFlag != NULL) scalable_free(pFlag);
	if(pHeap != NULL) scalable_free(pHeap);
}

// Dijkstra算法 Body
template <class Type>
class CXDijkstraBody 
{
	tbb::parallel_while< CXDijkstraBody<Type> >& m_xWhile; 
	XGraph<Type>* m_pGraph;
public:
	CXDijkstraBody( XGraph<Type>* pGraph, tbb::parallel_while< CXDijkstraBody<Type> >& w ) : m_pGraph(pGraph), m_xWhile(w) {};
	typedef int argument_type;
	void operator()( int nIndex ) const 
	{
		XDijkstraLine<Type>(m_pGraph, nIndex);
	}
};   

// Dijkstra算法 Stream
class CXDijkstraStream 
{
	int m_nPos;
	int	m_nSize;
public:
	CXDijkstraStream( int  nSize) : m_nSize(nSize), m_nPos(0){}
	bool pop_if_present( int& nIndex ) 
	{
		bool bRet = m_nPos < m_nSize;
		if( bRet ) nIndex = m_nPos++;
		return bRet;
	}
};    

// Dijkstra算法 并行版本
template <class Type>
void XDijkstraParallel( XGraph<Type>* pGraph ) 
{
	CXDijkstraStream xStream(pGraph->nNode);
	tbb::parallel_while< CXDijkstraBody<Type> > xWhile;
	xWhile.run(xStream, CXDijkstraBody<Type>(pGraph, xWhile));
}

// Dijkstra算法 串行版本
template <class Type>
void XDijkstraSerial( XGraph<Type>* pGraph ) 
{
	int nNode = pGraph->nNode;
	for(int i= 0; i < nNode; ++i) 	
	{   
		XDijkstraLine<uint32>(pGraph, i);
	}
}


#endif