最近做了路径搜索,看了网上的描述真是晦涩,所以自己就整理下!
图画的不太好, :)
绿色的是节点,红色的为权值,箭头为可通行的标志.
现在我们要从 0 节点 到 12 节点 找一条最优路径:
首先咱们要解决NODE点存贮的信息(结构):
struct NodeBaseInfo
{
unsigned short nNodeID; //番号
unsigned long nMeasure; //权值
NodeBaseInfo *pParent; //父节点
};
我写了简单的结构大家可以根据自己需要定义（定义这个结构是为了更好理解）
下面讲的是最主要的了：
DIJKSTAR算法中要定义两个表：OPEN 和 CLOSE （其实可以看作链表）
他的原理就是把没有遍历的点放在 OPEN 表中，把从 OPEN表中遍历到的最短权值的点放入
CLOSE 表中，当插入 CLOSE表中的节点的番号于我们要的重点时算法结束；然后按照父节点（pParent）
向上递归就可以得到我们要的最优路径了。
第一步：应为 OPEN 和CLOSE表都是空的，把起点（0节点）插入CLOSE标中，它的权值为0。把起点（0节点）附近的节点（因该为可通行的）插入OPEN 表中（最好按权值从大道小的顺序插入，这样取得最优值时，这样速度就会很快）。（如示例图）
第2步：从OPEN表中找到权值最小的节点，把它插入CLOSE 表中, 把这个节点的可连通的节点查入ＯＰＥＮ
表，（如果ＯＰＥＮ表中存在要查入的点，如果要插入的节点的权值比已经存在的小，就把已经查入的权值该为最小的，如果要插入的节点的权值比已经存在的大，就忽落它．）
（为了更好的理解我把父节点也加入了，如示例图）