缘起
最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用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 graph
import (
"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)
PASS
ok command-line-arguments 0.002s
INode.go
顶点接口
package bellman_fold
type INode interface {
ID() string
GetWeight() int
SetWeight(int)
}
const MaxWeight = int(0x7fffffff_ffffffff)
ILine.go
边接口
package bellman_fold
type ILine interface {
From() string
To() string
Weight() int
}
IPathFinder.go
最短路径查找算法接口
package bellman_fold
type IPathFinder interface {
FindPath(nodes []INode, lines []ILine, from string, to string) (bool,[]INode)
}
iNodeQueue.go
顶点队列接口, FIFO队列
package bellman_fold
type iNodeQueue interface {
Clear()
Size() int
Empty() bool
Push(node INode)
Poll() (bool, INode)
}
tNode.go
顶点, 实现INode
package bellman_fold
import "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_fold
type 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_fold
type 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_fold
type 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)
