缘起
最近浏览<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳golang练习之
贝尔曼-福特算法
贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短门路问题的算法。最短门路问题就是在加权图指定了终点和起点的前提下，寻找从终点到起点的门路中权重总和最小的那条门路。摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一流程
- 给定若干顶点, 以及顶点间的若干条边, 寻找从指定终点from到指定起点to的最小权重门路
- 设定from的权重为0, 其余顶点的权重为无穷大
- 将from节点送入候选队列
for 候选队列不为空:
- 从候选队列出队一个顶点node
- 遍历从node登程的所有边, 将边的起点权重, 更新为min(起点权重, node.权重+边.权重)
- 如果起点权重 > node.权重+边.权重, 阐明更新无效, 则将起点push到候选队列
- 判断起点的权重是否被更新(!=无穷大), 如果是则阐明存在最短门路
反向查找最短门路:
- 设定以后节点current = 起点
- push节点current进门路队列
- 遍历起点为current的边, 查找符合条件的node:边的终点.权重 = current.权重-边.权重
- push节点node进门路队列
- 循环1-4, 直到current == from, 查找实现
指标
- 实现并验证贝尔曼-福特算法
设计
- INode: 顶点接口
- ILine: 边接口
- IPathFinder: 最短门路查找算法接口
- iNodeQueue: 顶点队列接口, FIFO队列
- tNode: 顶点, 实现INode
- tLine: 边, 实现ILine
- tFIFOQueue: FIFO节点队列的实现
- tBellmanFoldFinder: 贝尔曼-福特算法的实现
单元测试
bellman_fold_test.go
package graphimport ( "fmt" bf "learning/gooop/graph/bellman_fold" "strings" "testing")func Test_BellmanFold(t *testing.T) { fnAssertTrue := func(b bool, msg string) { if !b { t.Fatal(msg) } } nodes := []bf.INode{ bf.NewNode("a"), bf.NewNode("b"), bf.NewNode("c"), bf.NewNode("d"), bf.NewNode("e"), bf.NewNode("f"), bf.NewNode("g"), } lines := []bf.ILine { bf.NewLine("a", "b", 9), bf.NewLine("a", "c", 2), bf.NewLine("b", "c", 6), bf.NewLine("b", "d", 3), bf.NewLine("b", "e", 1), bf.NewLine("c", "d", 2), bf.NewLine("c", "f", 9), bf.NewLine("d", "e", 5), bf.NewLine("d", "f", 6), bf.NewLine("e", "f", 3), bf.NewLine("e", "g", 7), bf.NewLine("f", "g", 4), } for _,it := range lines[:] { lines = append(lines, bf.NewLine(it.To(), it.From(), it.Weight())) } ok,path := bf.BellmanFoldFinder.FindPath(nodes, lines, "a", "g") if !ok { t.Fatal("failed to find min path") } fnPathToString := func(nodes []bf.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) fnAssertTrue(pathString == "a(0) c(2) d(4) f(10) g(14)", "incorrect path")}测试输入
$ go test -v bellman_fold_test.go === RUN Test_BellmanFold bellman_fold_test.go:63: a(0) c(2) d(4) f(10) g(14)--- PASS: Test_BellmanFold (0.00s)PASSok command-line-arguments 0.002sINode.go
顶点接口
package bellman_foldtype INode interface { ID() string GetWeight() int SetWeight(int)}const MaxWeight = int(0x7fffffff_ffffffff)ILine.go
边接口
package bellman_foldtype ILine interface { From() string To() string Weight() int}IPathFinder.go
最短门路查找算法接口
package bellman_foldtype IPathFinder interface { FindPath(nodes []INode, lines []ILine, from string, to string) (bool,[]INode)}iNodeQueue.go
顶点队列接口, FIFO队列
package bellman_foldtype iNodeQueue interface { Clear() Size() int Empty() bool Push(node INode) Poll() (bool, INode)}tNode.go
顶点, 实现INode
package bellman_foldimport "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 bellman_foldtype 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}tFIFOQueue.go
FIFO节点队列的实现
package bellman_foldtype tFIFOQueue struct { nodes []INode capacity int rindex int windex int}func newFIFOQueue() iNodeQueue { it := &tFIFOQueue{} it.Clear() return it}func (me *tFIFOQueue) Clear() { me.nodes = make([]INode, 0) me.capacity = 0 me.rindex = -1 me.windex = -1}func (me *tFIFOQueue) Size() int { return me.windex - me.rindex}func (me *tFIFOQueue) Empty() bool { return me.Size() <= 0}func (me *tFIFOQueue) Push(node INode) { me.ensureSpace(1) me.windex++ me.nodes[me.windex] = node}func (me *tFIFOQueue) ensureSpace(size int) { for me.capacity < me.windex + size + 1 { me.nodes = append(me.nodes, nil) me.capacity++ }}func (me *tFIFOQueue) Poll() (bool, INode) { if me.Empty() { return false, nil } me.rindex++ it := me.nodes[me.rindex] me.nodes[me.rindex] = nil if me.rindex > me.capacity / 2 { size := me.Size() offset := me.rindex + 1 for i := 0;i < size;i++ { me.nodes[i], me.nodes[i + offset] = me.nodes[i + offset], nil } me.rindex -= offset me.windex -= offset } return true, it}tBellmanFoldFinder.go
贝尔曼-福特算法的实现
package bellman_foldtype tBellmanFoldFinder struct {}func newBellmanFoldFinder() IPathFinder { return &tBellmanFoldFinder{ }}func (me *tBellmanFoldFinder) FindPath(nodes []INode, lines []ILine, fromID string, toID string) (bool,[]INode) { // 节点索引 mapNodes := make(map[string]INode, 0) for _,it := range nodes { mapNodes[it.ID()] = it } fromNode, ok := mapNodes[fromID] if !ok { return false, nil } toNode,ok := mapNodes[toID] 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() == fromID { it.SetWeight(0) } else { it.SetWeight(MaxWeight) } } // 循环更新所有节点的权重 直到不再变动 fromNode.SetWeight(0) queue := newFIFOQueue() queue.Push(fromNode) for !queue.Empty() { ok,from := queue.Poll() if !ok { panic("unexpected !ok") } affectedLines, ok := mapFromLines[from.ID()] if ok { for _,line := range affectedLines { if to,ok := mapNodes[line.To()];ok { if me.updateWeight(from, to, line) { queue.Push(to) } } } } } // 逆向查找最短门路 if toNode.GetWeight() >= MaxWeight { return false, nil } queue.Clear() queue.Push(toNode) current := toNode maxRound := len(lines) for ;current != fromNode && maxRound > 0;maxRound-- { linkedLines, _ := mapToLines[current.ID()] for _,line := range linkedLines { from, _ := mapNodes[line.From()] if from.GetWeight() == current.GetWeight() - line.Weight() { current = from queue.Push(from) } } } if current != fromNode { return false, nil } // 返回 result := make([]INode, queue.Size()) for i := queue.Size() - 1;i >= 0;i-- { _,result[i] = queue.Poll() } return true, result}func (me *tBellmanFoldFinder) 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 *tBellmanFoldFinder) min(a, b int) int { if a <= b { return a } return b}var BellmanFoldFinder = newBellmanFoldFinder()(end)