dijkstrasearch.h

Dijkstra算法及demo实现

#pragma once
#include "Node.h"

double DegreesToMeters(double x1, double y1, double x2, double y2);

///////////////////////////////////////////////////////////////////////////////////////////
//物理结点,根据实际来重写
typedef unsigned long ValueType;               //权重数据类型
#define OBJECT_MAXVALUE (0xffffffff)           //权重为最大(无限)

class SearchObject
{
public:
	SearchObject(){};
	~SearchObject(){};

public:
	unsigned long id;
	double        x;
	double        y;
	
public://以下方法必须实现
	inline ValueType GetValue(SearchObject &Object,int nType) const
	{
		return (ValueType)DegreesToMeters(x,Object.x,y,Object.y);
		/*ValueType tx=(ValueType)(x-Object.x);
		ValueType ty=(ValueType)(y-Object.y);
		return (ValueType)sqrt((double)(tx*tx+ty*ty));*/
	}

	inline int IsSame(SearchObject &so) const
	{
		if(x==so.x && y==so.y) 
			return 1;
		else
			return 0;
	}

	inline int operator== (SearchObject &so) const
	{
		return IsSame(so);
	}

	inline int operator!= (SearchObject &so) const
	{
		return !IsSame(so);
	}
};

typedef NodeList<SearchObject*> SearchObjectList;
///////////////////////////////////////////////////////////////////////////////////////////
//内存结点
typedef struct _MemSearchObject MemSearchObject;
typedef NodeList<MemSearchObject*> MemSearchObjectList;

typedef struct _MemSearchObject
{
	SearchObject          m_OwnerObject;           //结点数据
	MemSearchObjectList   m_pNextMemObjectList;    //相邻结点列表
	MemSearchObjectList   m_pLeftNextMemObjectList;//内部使用,还没有使用的剩余连接数
}MemSearchObject,*PMemSearchObject;
///////////////////////////////////////////////////////////////////////////////////////////
//内存临时搜索结果
typedef struct _MemSearchResult
{
	struct _MemSearchResult *m_pParent;            //线路父结点
	MemSearchObject         *m_pMemObject;         //线路末结点
	ValueType               m_vValue;              //路线总权重
}MemSearchResult,*P_MemSearchResult;

typedef NodeList<MemSearchResult*> MemSearchResultList;
///////////////////////////////////////////////////////////////////////////////////////////
//搜索实现对象
class CDijkstraSearch
{
public:
	CDijkstraSearch(void);
	~CDijkstraSearch(void);

public:
	bool InitSearch(MemSearchObject *pMemObjectList,long nObjectCount);
	bool StartSearch(MemSearchObject *pBeginObject,MemSearchObject *pEndObject,int nType,SearchObjectList *pSearchResult);

public:
	static bool ConnectObject(MemSearchObject *pFirst,MemSearchObject *pSecond,bool bBoth=true);

private:
	MemSearchObject *m_pMemObjectList;
	long             m_nObjectCount;
};