缘起
最近浏览<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳golang练习之
狄克斯特拉算法
与贝尔曼-福特算法相似，狄克斯特拉（Dijkstra）算法也是求解最短门路问题的算法，应用它能够求得从终点到起点的门路中权重总和最小的那条门路。比起须要对所有的边都反复计算权重和更新权重的贝尔曼-福特算法，狄克斯特拉算法多了一步抉择顶点的操作，这使得它在求最短门路上更为高效。如果闭环中有正数权重，就不存在最短门路。贝尔曼-福特算法能够间接认定不存在最短门路，但在狄克斯特拉算法中，即使不存在最短门路，它也会算出一个谬误的最短门路进去。因而，有正数权重时不能应用狄克斯特拉算法。摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一- 狄克斯特拉算法与贝尔曼-福特算法十分类似, 次要区别在于总是优先选择权重最小的候选节点.
- 因而, 贝尔曼-福特算法应用队列或堆栈存储候选节点, 而狄克斯特拉算法应用堆.
流程
- 给定若干顶点, 以及顶点间的若干条边, 寻找从指定终点srcNode到指定起点dstNode的最小权重门路
- 设定srcNode的权重为0, 其余顶点的权重为无穷大
- 将srcNode节点送入候选堆
for 候选堆不为空:
- 从候选堆pop顶点node
- 如果node.id == dstNode.id, 循环完结
- 遍历从node登程的所有边, 将边的起点to的权重, 更新为min(起点权重, node.权重+边.权重)
- 如果to.权重 > node.权重+边.权重, 阐明更新无效
- 如果更新无效, 判断to是否在堆中, 如果是, 则上浮以保护堆秩序, 否则, 将to节点push入候选堆
- 判断起点的权重是否被更新(!=无穷大), 如果是则阐明存在最短门路
反向查找最短门路:
- 设定以后节点current = 起点
- push节点current进门路队列
- 遍历起点为current的边, 查找符合条件的node:边的终点.权重 = current.权重-边.权重
- push节点node进门路队列
- 循环1-4, 直到current == srcNode, 查找实现
设计
- INode: 顶点接口
- ILine: 边接口
- IPathFinder: 最短门路查找算法接口
- IComparator: 顶点比拟接口
- IHeap: 顶点堆接口
- tNode: 顶点, 实现INode
- tLine: 边, 实现ILine
- tNodeWeightComparator: 基于权重的顶点比拟器, 实现IComparator接口
- tArrayHeap: 堆的实现
- tDijkstraPathFinder: 狄克斯特拉算法的实现
单元测试
dijkstra_finder_test.go
package graphimport ( "fmt" dk "learning/gooop/graph/dijkstra" "strings" "testing")func Test_DijkstraFinder(t *testing.T) { fnAssertTrue := func(b bool, msg string) { if !b { t.Fatal(msg) } } nodes := []dk.INode{ dk.NewNode("a"), dk.NewNode("b"), dk.NewNode("c"), dk.NewNode("d"), dk.NewNode("e"), dk.NewNode("f"), dk.NewNode("g"), } lines := []dk.ILine { dk.NewLine("a", "b", 9), dk.NewLine("a", "c", 2), dk.NewLine("b", "c", 6), dk.NewLine("b", "d", 3), dk.NewLine("b", "e", 1), dk.NewLine("c", "d", 2), dk.NewLine("c", "f", 9), dk.NewLine("d", "e", 5), dk.NewLine("d", "f", 6), dk.NewLine("e", "f", 3), dk.NewLine("e", "g", 7), dk.NewLine("f", "g", 4), } for _,it := range lines[:] { lines = append(lines, dk.NewLine(it.To(), it.From(), it.Weight())) } ok,path := dk.DijkstraPathFinder.FindPath(nodes, lines, "a", "g") if !ok { t.Fatal("failed to find min path") } fnPathToString := func(nodes []dk.INode) string { items := make([]string, len(nodes)) for i,it := range nodes { items[i] = fmt.Sprintf("%s", it) } return strings.Join(items, " ") } pathString := fnPathToString(path) t.Log(pathString) fnAssertTrue(pathString == "a(0) c(2) d(4) f(10) g(14)", "incorrect path")}测试输入
$ go test -v dijkstra_finder_test.go === RUN Test_DijkstraFinder dijkstra_finder_test.go:63: a(0) c(2) d(4) f(10) g(14)--- PASS: Test_DijkstraFinder (0.00s)PASSok command-line-arguments 0.001sINode.go
顶点接口
package dijkstratype INode interface { ID() string GetWeight() int SetWeight(int)}const MaxWeight = int(0x7fffffff_ffffffff)ILine.go
边接口
package dijkstratype ILine interface { From() string To() string Weight() int}IPathFinder.go
最短门路查找算法接口
package dijkstratype IPathFinder interface { FindPath(nodes []INode, lines []ILine, from string, to string) (bool,[]INode)}IComparator.go
顶点比拟接口
package dijkstratype IComparator interface { Less(a interface{}, b interface{}) bool}IHeap.go
顶点堆接口
package dijkstratype IHeap interface { Size() int IsEmpty() bool IsNotEmpty() bool Push(node interface{}) Pop() (bool, interface{}) IndexOf(node interface{}) int ShiftUp(i int)}tNode.go
顶点, 实现INode
package dijkstraimport "fmt"type tNode struct { id string weight int}func NewNode(id string) INode { return &tNode{ id,MaxWeight, }}func (me *tNode) ID() string { return me.id}func (me *tNode) GetWeight() int { return me.weight}func (me *tNode) SetWeight(w int) { me.weight = w}func (me *tNode) String() string { return fmt.Sprintf("%s(%v)", me.id, me.weight)}tLine.go
边, 实现ILine
package dijkstratype tLine struct { from string to string weight int}func NewLine(from string, to string, weight int) ILine { return &tLine{ from,to,weight, }}func (me *tLine) From() string { return me.from}func (me *tLine) To() string { return me.to}func (me *tLine) Weight() int { return me.weight}tNodeWeightComparator.go
基于权重的顶点比拟器, 实现IComparator接口
package dijkstraimport "errors"type tNodeWeightComparator struct {}func newNodeWeightComparator() IComparator { return &tNodeWeightComparator{ }}func (me *tNodeWeightComparator) Less(a interface{}, b interface{}) bool { if a == nil || b == nil { panic(gNullArgumentError) } n1 := a.(INode) n2 := b.(INode) return n1.GetWeight() <= n2.GetWeight()}var gNullArgumentError = errors.New("null argument error")tArrayHeap.go
堆的实现
package dijkstraimport ( "errors" "fmt" "strings")type tArrayHeap struct { comparator IComparator items []interface{} size int version int64}func newArrayHeap(comparator IComparator) IHeap { return &tArrayHeap{ comparator: comparator, items: make([]interface{}, 0), size: 0, version: 0, }}func (me *tArrayHeap) Size() int { return me.size}func (me *tArrayHeap) IsEmpty() bool { return me.size <= 0}func (me *tArrayHeap) IsNotEmpty() bool { return !me.IsEmpty()}func (me *tArrayHeap) Push(value interface{}) { me.version++ me.ensureSize(me.size + 1) me.items[me.size] = value me.size++ me.ShiftUp(me.size - 1) me.version++}func (me *tArrayHeap) ensureSize(size int) { for ;len(me.items) < size; { me.items = append(me.items, nil) }}func (me *tArrayHeap) parentOf(i int) int { return (i - 1) / 2}func (me *tArrayHeap) leftChildOf(i int) int { return i*2 + 1}func (me *tArrayHeap) rightChildOf(i int) int { return me.leftChildOf(i) + 1}func (me *tArrayHeap) last() (i int, v interface{}) { if me.IsEmpty() { return -1, nil } i = me.size - 1 v = me.items[i] return i,v}func (me *tArrayHeap) IndexOf(node interface{}) int { n := -1 for i,it := range me.items { if it == node { n = i break } } return n}func (me *tArrayHeap) ShiftUp(i int) { if i <= 0 { return } v := me.items[i] pi := me.parentOf(i) pv := me.items[pi] if me.comparator.Less(v, pv) { me.items[pi], me.items[i] = v, pv me.ShiftUp(pi) }}func (me *tArrayHeap) Pop() (bool, interface{}) { if me.IsEmpty() { return false, nil } me.version++ top := me.items[0] li, lv := me.last() me.items[0] = nil me.size-- if me.IsEmpty() { return true, top } me.items[0] = lv me.items[li] = nil me.shiftDown(0) me.version++ return true, top}func (me *tArrayHeap) shiftDown(i int) { pv := me.items[i] ok, ci, cv := me.minChildOf(i) if ok && me.comparator.Less(cv, pv) { me.items[i], me.items[ci] = cv, pv me.shiftDown(ci) }}func (me *tArrayHeap) minChildOf(p int) (ok bool, i int, v interface{}) { li := me.leftChildOf(p) if li >= me.size { return false, 0, nil } lv := me.items[li] ri := me.rightChildOf(p) if ri >= me.size { return true, li, lv } rv := me.items[ri] if me.comparator.Less(lv, rv) { return true, li, lv } else { return true, ri, rv }}func (me *tArrayHeap) String() string { level := 0 lines := make([]string, 0) lines = append(lines, "") for { n := 1<<level min := n - 1 max := n + min - 1 if min >= me.size { break } line := make([]string, 0) for i := min;i <= max;i++ { if i >= me.size { break } line = append(line, fmt.Sprintf("%4d", me.items[i])) } lines = append(lines, strings.Join(line, ",")) level++ } return strings.Join(lines, "\n")}var gNoMoreElementsError = errors.New("no more elements")tDijkstraPathFinder.go
狄克斯特拉算法的实现
package dijkstratype tDijkstraPathFinder struct {}func newDijkstraPathFinder() IPathFinder { return &tDijkstraPathFinder{}}func (me *tDijkstraPathFinder) FindPath(nodes []INode, lines []ILine, srcID string, dstID string) (bool,[]INode) { // 节点索引 mapNodes := make(map[string]INode, 0) for _,it := range nodes { mapNodes[it.ID()] = it } srcNode, ok := mapNodes[srcID] if !ok { return false, nil } dstNode,ok := mapNodes[dstID] if !ok { return false, nil } // 边的索引 mapFromLines := make(map[string][]ILine, 0) mapToLines := make(map[string][]ILine, 0) for _, it := range lines { if v,ok := mapFromLines[it.From()];ok { mapFromLines[it.From()] = append(v, it) } else { mapFromLines[it.From()] = []ILine{ it } } if v,ok := mapToLines[it.To()];ok { mapToLines[it.To()] = append(v, it) } else { mapToLines[it.To()] = []ILine{ it } } } // 设置from节点的weight为0, 其余节点的weight为MaxWeight for _,it := range nodes { if it.ID() == srcID { it.SetWeight(0) } else { it.SetWeight(MaxWeight) } } // 将终点push到堆 heap := newArrayHeap(newNodeWeightComparator()) heap.Push(srcNode) // 遍历候选节点 for heap.IsNotEmpty() { _, top := heap.Pop() from := top.(INode) if from.ID() == dstID { break } links, ok := mapFromLines[from.ID()] if ok { for _,line := range links { if to,ok := mapNodes[line.To()];ok { if me.updateWeight(from, to, line) { n := heap.IndexOf(to) if n >= 0 { heap.ShiftUp(n) } else { heap.Push(to) } } } } } } // 逆向查找最短门路 if dstNode.GetWeight() >= MaxWeight { return false, nil } path := []INode{ dstNode } current := dstNode maxRound := len(lines) for ;current != srcNode && maxRound > 0;maxRound-- { linkedLines, _ := mapToLines[current.ID()] for _,line := range linkedLines { from, _ := mapNodes[line.From()] if from.GetWeight() == current.GetWeight() - line.Weight() { current = from path = append(path, from) } } } if current != srcNode { return false, nil } me.reverse(path) return true, path}func (me *tDijkstraPathFinder) reverse(nodes []INode) { for i,j := 0, len(nodes)-1;i < j;i,j=i+1,j-1 { nodes[i], nodes[j] = nodes[j], nodes[i] }}func (me *tDijkstraPathFinder) updateWeight(from INode, to INode, line ILine) bool { w := me.min(from.GetWeight() + line.Weight(), to.GetWeight()) if to.GetWeight() > w { to.SetWeight(w) return true } return false}func (me *tDijkstraPathFinder) min(a, b int) int { if a <= b { return a } return b}var DijkstraPathFinder = newDijkstraPathFinder()(end)