最近做了路徑搜索,看了網(wǎng)上的描述真是晦澀,所以自己就整理下!
圖畫(huà)的不太好, :)
綠色的是節(jié)點(diǎn),紅色的為權(quán)值,箭頭為可通行的標(biāo)志.
現(xiàn)在我們要從 0 節(jié)點(diǎn) 到 12 節(jié)點(diǎn) 找一條最優(yōu)路徑:
首先咱們要解決NODE點(diǎn)存貯的信息(結(jié)構(gòu)):
struct NodeBaseInfo
{
unsigned short nNodeID; //番號(hào)
unsigned long nMeasure; //權(quán)值
NodeBaseInfo *pParent; //父節(jié)點(diǎn)
};
我寫了簡(jiǎn)單的結(jié)構(gòu)大家可以根據(jù)自己需要定義（定義這個(gè)結(jié)構(gòu)是為了更好理解）
下面講的是最主要的了：
DIJKSTAR算法中要定義兩個(gè)表：OPEN 和 CLOSE （其實(shí)可以看作鏈表）
他的原理就是把沒(méi)有遍歷的點(diǎn)放在 OPEN 表中，把從 OPEN表中遍歷到的最短權(quán)值的點(diǎn)放入
CLOSE 表中，當(dāng)插入 CLOSE表中的節(jié)點(diǎn)的番號(hào)于我們要的重點(diǎn)時(shí)算法結(jié)束；然后按照父節(jié)點(diǎn)（pParent）
向上遞歸就可以得到我們要的最優(yōu)路徑了。
第一步：應(yīng)為 OPEN 和CLOSE表都是空的，把起點(diǎn)（0節(jié)點(diǎn)）插入CLOSE標(biāo)中，它的權(quán)值為0。把起點(diǎn)（0節(jié)點(diǎn)）附近的節(jié)點(diǎn)（因該為可通行的）插入OPEN 表中（最好按權(quán)值從大道小的順序插入，這樣取得最優(yōu)值時(shí)，這樣速度就會(huì)很快）。（如示例圖）
第2步：從OPEN表中找到權(quán)值最小的節(jié)點(diǎn)，把它插入CLOSE 表中, 把這個(gè)節(jié)點(diǎn)的可連通的節(jié)點(diǎn)查入ＯＰＥＮ
表，（如果ＯＰＥＮ表中存在要查入的點(diǎn)，如果要插入的節(jié)點(diǎn)的權(quán)值比已經(jīng)存在的小，就把已經(jīng)查入的權(quán)值該為最小的，如果要插入的節(jié)點(diǎn)的權(quán)值比已經(jīng)存在的大，就忽落它．）
（為了更好的理解我把父節(jié)點(diǎn)也加入了，如示例圖）