最近做了路徑搜索,看了網上的描述真是晦澀,所以自己就整理下!
圖畫的不太好, :)
綠色的是節點,紅色的為權值,箭頭為可通行的標志.
現在我們要從 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 表中, 把這個節點的可連通的節點查入ＯＰＥＮ
表，（如果ＯＰＥＮ表中存在要查入的點，如果要插入的節點的權值比已經存在的小，就把已經查入的權值該為最小的，如果要插入的節點的權值比已經存在的大，就忽落它．）
（為了更好的理解我把父節點也加入了，如示例圖）