【文件属性】：
文件名称：Dijkstra 算法原理
文件大小：19KB
文件格式：RAR
更新时间：2012-11-17 03:26:53
Dijkstra
讲解 Dijkstra 算法的基本思想，另外还有算法实现. 当然了，这个算法当路径点上万的时候效率上会降低。 我有另外的改进实现， 上万个点也是在200毫秒内完成。但是不知道怎么添加， 我只能在这里贴关键代码了 ：
static std::list
vecNodes;
static std::list vecEdges;
bool CDijkstras::DijkstrasFindPath(Node* psrcNode, Node* pdstNode, std::list& vec, double& fromSrcDist)
{
if (psrcNode == 0 || pdstNode == 0) return false;
if (psrcNode == pdstNode)
{
vec.push_back(pdstNode);
return false;
}
std::list::const_iterator it;
for (it=vecNodes.begin(); it!=vecNodes.end(); it++)
{
(*it)->bAdded = false;
(*it)->previous = 0;
(*it)->distanceFromStart = MAXDOUBLE;
(*it)->smallest = 0;
}
bool bFindDst = DijkstrasRouteInitialize(psrcNode, pdstNode);
fromSrcDist = pdstNode->distanceFromStart;
Node* previous = pdstNode;
while (previous)
{
vec.push_back(previous);
previous = previous->previous;
}
m_pDstNode = pdstNode;
return bFindDst;
}
bool CDijkstras::DijkstrasRouteInitialize(Node* psrcNode, Node* pdstNode)
{
bool bFindDst = false;
psrcNode->distanceFromStart = 0;
Node* smallest = psrcNode;
smallest->bAdded = true;
std::list::const_iterator it, ait;
std::list AdjAdjNodes ;
for (it=psrcNode->connectNodes.begin(); it!=psrcNode->connectNodes.end(); it++)
{
if ((*it)->bAdded) continue;
(*it)->smallest = psrcNode;
(*it)->bAdded = true;
AdjAdjNodes.push_back(*it);
}
while (1)
{
std::list tempAdjAdjNodes;
for (it=AdjAdjNodes.begin(); it!=AdjAdjNodes.end(); it++)
{
Node* curNode = *it;
for (ait=curNode->connectNodes.begin(); ait!=curNode->connectNodes.end(); ait++)
{
Node* pns = *ait;
double distance = Distance(pns, curNode) + pns->distanceFromStart;
if (distance < curNode->distanceFromStart)
{
curNode->distanceFromStart = distance;
curNode->previous = pns;
}
if (pns->bAdded == false)
{
tempAdjAdjNodes.push_back(pns);
pns->bAdded = true;
}
}
if (curNode == pdstNode)
{
bFindDst = true;
}
}
if (bFindDst)
break;
if (tempAdjAdjNodes.size() == 0)
break;
AdjAdjNodes.clear();
AdjAdjNodes = tempAdjAdjNodes;
}
return bFindDst;
}
// Return distance between two connected nodes
float CDijkstras::Distance(Node* node1, Node* node2)
{
std::list::const_iterator it;
for (it=node1->connectEdges.begin(); it!=node1->connectEdges.end(); it++)
{
if ( (*it)->node1 == node2 || (*it)->node2 == node2 )
return (*it)->distance;
}
#ifdef _DEBUG
__asm {int 3};
#endif
return (float)ULONG_MAX;
}
/****************************************************************************/
/****************************************************************************/
/****************************************************************************/
//得到区域的Key//
__int64 CDijkstras::GetRegionKey( float x, float z )
{
long xRegion = (long)(x / m_regionWidth);
long zRegion = (long)(z / m_regionHeight);
__int64 key = xRegion;
key <<= 32;
key |= ( zRegion & 0x00000000FFFFFFFF );
return key;
}
//得到区域的Key//
__int64 CDijkstras::GetRegionKey( long tx, long tz )
{
long xRegion = tx ;
long zRegion = tz ;
__int64 key = xRegion;
key <<= 32;
key |= ( zRegion & 0x00000000FFFFFFFF );
return key;
}
//取得一个区域内的所有的路径点, 返回添加的路径点的个数//
unsigned long CDijkstras::GetRegionWaypoint (__int64 rkey, std::vector& vec)
{
unsigned long i = 0;
SAME_RANGE_NODE rangeNode = mmapWaypoint.equal_range(rkey);
for (CRWPIT it=rangeNode.first; it!=rangeNode.second; it++)
{
i++;
Node* pn = it->second;
vec.push_back(pn);
}
return i;
}
inline bool cmdDistanceNode (Node* pNode1, Node* pNode2)
{
return pNode1->cmpFromStart < pNode2->cmpFromStart;
};
//添加一个路径点//
Node* CDijkstras::AddNode (unsigned long id, float x, float y, float z)
{
Node* pNode = new Node(id, x, y, z);
__int64 rkey = GetRegionKey(x, z);
mmapWaypoint.insert(make_pair(rkey, pNode));
mapID2Node[id] = pNode;
return pNode;
}
//添加一条边//
Edge* CDijkstras::AddEdge (Node* node1, Node* node2, float fCost)
{
Edge* e = new Edge (node1, node2, fCost);
return e;
}
//通过路径点ID得到路径点的指针//
Node* CDijkstras::GetNodeByID (unsigned long nid)
{
std::map::const_iterator it;
it = mapID2Node.find(nid);
if (it!=mapID2Node.end())
return it->second;
return NULL;
}
【文件预览】：
Dijkstras+algorithm.ppt
dijkstras-source-code.zip
