算法思想?
?從起始點(diǎn)開始葛超，采用貪心算法的策略，每次遍歷到始點(diǎn)距離最近且未訪問過的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止津畸。 每次選擇距離起始點(diǎn)最近的節(jié)點(diǎn), 然后以此不斷向外擴(kuò)展, 直至達(dá)到終點(diǎn)
?算法描述(步驟)?
1: 定義集合, S = {u}, Q= v - S, 定義dist: 起始點(diǎn)距離其他節(jié)點(diǎn)的距離?
2: 在Q中找出距離起點(diǎn)最近的節(jié)點(diǎn)加入 S中, 然后更新dist
?3: 重復(fù)2, 直接Q集合為空, dist就是所求的內(nèi)容 比較難理解的算法需要演練下?
算法偽代碼實(shí)現(xiàn)
?1: 定義visit數(shù)組: 為1代表已經(jīng)被訪問過?
find u-> minQ(u) && visit[u] == 0?
update dist[i]: if dist[i] > dist[u]+cost[i][u]?
2: 使用最小堆做優(yōu)化?
get minQ(u) in minheap?
update dist[i]: if dist[i] > dist[u]+cost[i][u]
?有興趣寫下具體實(shí)現(xiàn)
```
type?nodeinfo?struct?{
????targetNode?int
????distance?int
????index?int
}
type?nodeinfos?[]*nodeinfo
const?Inf?=?1e9
func?(nodes?*nodeinfos)?Len()?int?{
????return?len(*nodes)
}
func?(nodes?*nodeinfos)?Less(i,?j?int)?bool?{
????return?(*nodes)[i].distance?<?(*nodes)[j].distance
}
func?(nodes?*nodeinfos)?Swap(i,?j?int)?{
????(*nodes)[i],?(*nodes)[j]?=?(*nodes)[j],?(*nodes)[i]
????(*nodes)[i].index?=?i
????(*nodes)[j].index?=?j
}
func?(nodes?*nodeinfos)?Push(x?interface{})?{
????n?:=?len(*nodes)
????item?:=?x.(*nodeinfo)
????item.index?=?n
????*nodes?=?append(*nodes,?item)
}
func?(nodes?*nodeinfos)?Pop()?interface{}?{
????if?len((*nodes))?<=?0?{
????????return?nil
????}
????x?:=?(*nodes)[len((*nodes))-1]
????(*nodes)?=?(*nodes)[:len((*nodes))-1]
????return?x
}
//n個(gè)節(jié)點(diǎn)，?k為起始節(jié)點(diǎn)必怜，?cost為鄰接矩陣
func?Dijkstra(cost?[][]int,?N?int,?start?int,?end?int)?(res?[][]int)?{
????dist?:=?make([]int,?N)
????for?i?:=?0;?i?<?N;?i++?{
????????dist[i]?=?Inf
????}
????dist[start]?=?0
????nodemap?:=?map[int]*nodeinfo{}
????heapElement?:=?make(nodeinfos,?0)
????heap.Init(&heapElement)
????nodeptr?:=?&nodeinfo{
????????targetNode:?start,
????????distance:?0,
????}
????heap.Push(&heapElement,?nodeptr)
????nodemap[start]?=?nodeptr
????relayNodes?:=?make([][]int,?N)//源節(jié)點(diǎn)到各節(jié)點(diǎn)的最后一個(gè)中轉(zhuǎn)節(jié)點(diǎn)
????for?i?:=?0;?i?<?N;?i++?{
????????relayNodes[i]?=?make([]int,?0)
????}
????relayNodes[start]?=?append(relayNodes[start],?start)
????for?len(heapElement)?>?0?{
????????minNode?:=?heap.Pop(&heapElement).(*nodeinfo)
????????delete(nodemap,?minNode.targetNode)
????????if?minNode.targetNode?==?end?{
????????????res?=?getAllTreePaths(relayNodes,?start,?end)
????????????return
????????}
????????for?i?:=?0;?i?<?N;?i++?{
????????????if?cost[minNode.targetNode][i]?==?Inf?{
????????????????continue
????????????}
????????????distance?:=?dist[minNode.targetNode]?+?cost[minNode.targetNode][i]
????????????if?distance?<?dist[i]?{
????????????????relayNodes[i]?=?make([]int,?0)
????????????}
????????????if?distance?<=?dist[i]?&&?i?!=?minNode.targetNode?{
????????????????relayNodes[i]?=?append(relayNodes[i],?minNode.targetNode)
????????????}
????????????if?distance?<?dist[i]?{
????????????????dist[i]?=?distance
????????????????if?value,?ok?:=?nodemap[i];?ok?{
????????????????????value.distance?=?distance
????????????????????heap.Fix(&heapElement,?value.index)
????????????????}?else?{
????????????????????heap.Push(&heapElement,?&nodeinfo{
????????????????????????targetNode:?i,
????????????????????????distance:?distance,
????????????????????})
????????????????}
????????????}
????????}
????}
????return
}
func?getAllTreePaths(relayNodes?[][]int,?start?int,?end?int)?[][]int?{
????path?:=?make([]int,?0)
????allpath?:=?[][]int{}
????getAllResults(relayNodes,?start,?end,?path,?&allpath)
????length?:=?len(allpath)?-?1
????for?i?:=?0;?i?<=?length;?i++?{
????????length2?:=?len(allpath[i])
????????for?j?:=?0;?j?<?length2?/?2;?j++?{
????????????allpath[i][j],?allpath[i][length2-j-1]?=?allpath[i][length2-j-1],?allpath[i][j]
????????}
????}
????return?allpath
}
func?getAllResults(relayNodes?[][]int,?start?int,?end?int,?path?[]int,?allpath?*[][]int)??{
????if?(start?==?end?||?len(relayNodes[end])?==?0)?{
????????path?=?append(path,?end)
????????*allpath?=?append(*allpath,?path)
????????return
????}
????path?=?append(path,?end)
????nodes?:=?relayNodes[end]
????for?i?:=?0;?i?<?len(nodes);?i++?{
????????getAllResults(relayNodes,?start,?nodes[i],?path,?allpath)
????}
}
注意: 有關(guān)堆的使用可以看:? go自帶的test用例, 寫的比較好, 特別是fix使用方法值得學(xué)習(xí)
```
應(yīng)用場景?
? 1: 從地點(diǎn)a達(dá)到地點(diǎn)b, 如何走最短?
? 2: 有關(guān)求最短路徑或者最短步驟的, 都可以試著把問題抽象成圖, 然后解之
擴(kuò)展算法
? ? Floyd算法等
