算法思想
从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 每次选择距离起始点最近的节点, 然后以此不断向外扩展, 直至达到终点
算法描述(步骤)
1: 定义集合, S = {u}, Q= v - S, 定义dist: 起始点距离其他节点的距离
2: 在Q中找出距离起点最近的节点加入 S中, 然后更新dist
3: 重复2, 直接Q集合为空, dist就是所求的内容 比较难理解的算法需要演练下
算法伪代码实现
1: 定义visit数组: 为1代表已经被访问过
find u-> minQ(u) && visit[u] == 0
update dist[i]: if dist[i] > dist[u]+cost[i][u]
2: 使用最小堆做优化
get minQ(u) in minheap
update dist[i]: if dist[i] > dist[u]+cost[i][u]
有兴趣写下具体实现
```
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个节点， k为起始节点， 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)//源节点到各节点的最后一个中转节点
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)
}
}
注意: 有关堆的使用可以看: go自带的test用例, 写的比较好, 特别是fix使用方法值得学习
```
应用场景
1: 从地点a达到地点b, 如何走最短?
2: 有关求最短路径或者最短步骤的, 都可以试着把问题抽象成图, 然后解之
扩展算法
Floyd算法等
