缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

贝尔曼-福特算法

  1. 贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。
  2. 最短路径问题就是在加权图指定了起点和终点的前提下，
  3. 寻找从起点到终点的路径中权重总和最小的那条路径。
  5. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

流程

  1. 给定若干顶点, 以及顶点间的若干条边, 寻找从指定起点from到指定终点to的最小权重路径
  2. 设定from的权重为0, 其他顶点的权重为无穷大
  3. 将from节点送入候选队列
  4. for 候选队列不为空:
    1. 从候选队列出队一个顶点node
    2. 遍历从node出发的所有边, 将边的终点权重, 更新为min(终点权重, node.权重+边.权重)
    3. 如果终点权重 > node.权重+边.权重, 说明更新有效, 则将终点push到候选队列
  5. 判断终点的权重是否被更新(!=无穷大), 如果是则说明存在最短路径
  6. 反向查找最短路径:
    1. 设定当前节点current = 终点
    2. push节点current进路径队列
    3. 遍历终点为current的边, 查找符合条件的node:边的起点.权重 = current.权重-边.权重
    4. push节点node进路径队列
    5. 循环1-4, 直到current == from, 查找完成

目标

  • 实现并验证贝尔曼-福特算法

设计

  • INode: 顶点接口
  • ILine: 边接口
  • IPathFinder: 最短路径查找算法接口
  • iNodeQueue: 顶点队列接口, FIFO队列
  • tNode: 顶点, 实现INode
  • tLine: 边, 实现ILine
  • tFIFOQueue: FIFO节点队列的实现
  • tBellmanFoldFinder: 贝尔曼-福特算法的实现

单元测试

bellman_fold_test.go

  1. package graph
  3. import (
  4.     "fmt"
  5.     bf "learning/gooop/graph/bellman_fold"
  6.     "strings"
  7.     "testing"
  8. )
  10. func Test_BellmanFold(t *testing.T) {
  11.     fnAssertTrue := func(b bool, msg string) {
  12.         if !b {
  13.             t.Fatal(msg)
  14.         }
  15.     }
  17.     nodes := []bf.INode{
  18.         bf.NewNode("a"),
  19.         bf.NewNode("b"),
  20.         bf.NewNode("c"),
  21.         bf.NewNode("d"),
  22.         bf.NewNode("e"),
  23.         bf.NewNode("f"),
  24.         bf.NewNode("g"),
  25.     }
  27.     lines := []bf.ILine {
  28.         bf.NewLine("a", "b", 9),
  29.         bf.NewLine("a", "c", 2),
  31.         bf.NewLine("b", "c", 6),
  32.         bf.NewLine("b", "d", 3),
  33.         bf.NewLine("b", "e", 1),
  35.         bf.NewLine("c", "d", 2),
  36.         bf.NewLine("c", "f", 9),
  38.         bf.NewLine("d", "e", 5),
  39.         bf.NewLine("d", "f", 6),
  41.         bf.NewLine("e", "f", 3),
  42.         bf.NewLine("e", "g", 7),
  44.         bf.NewLine("f", "g", 4),
  45.     }
  47.     for _,it := range lines[:] {
  48.         lines = append(lines, bf.NewLine(it.To(), it.From(), it.Weight()))
  49.     }
  51.     ok,path := bf.BellmanFoldFinder.FindPath(nodes, lines, "a", "g")
  52.     if !ok {
  53.         t.Fatal("failed to find min path")
  54.     }
  55.     fnPathToString := func(nodes []bf.INode) string {
  56.         items := make([]string, len(nodes))
  57.         for i,it := range nodes {
  58.             items[i] = fmt.Sprintf("%s", it)
  59.         }
  60.         return strings.Join(items, " ")
  61.     }
  62.     pathString := fnPathToString(path)
  63.     fnAssertTrue(pathString == "a(0) c(2) d(4) f(10) g(14)", "incorrect path")
  64. }

测试输出

  1. $ go test -v bellman_fold_test.go 
  2. === RUN   Test_BellmanFold
  3.     bellman_fold_test.go:63: a(0) c(2) d(4) f(10) g(14)
  4. --- PASS: Test_BellmanFold (0.00s)
  5. PASS
  6. ok      command-line-arguments  0.002s

INode.go

顶点接口

  1. package bellman_fold
  3. type INode interface {
  4.     ID() string
  5.     GetWeight() int
  6.     SetWeight(int)
  7. }
  9. const MaxWeight = int(0x7fffffff_ffffffff)

ILine.go

边接口

  1. package bellman_fold
  3. type ILine interface {
  4.     From() string
  5.     To() string
  6.     Weight() int
  7. }

IPathFinder.go

最短路径查找算法接口

  1. package bellman_fold
  3. type IPathFinder interface {
  4.     FindPath(nodes []INode, lines []ILine, from string, to string) (bool,[]INode)
  5. }

iNodeQueue.go

顶点队列接口, FIFO队列

  1. package bellman_fold
  3. type iNodeQueue interface {
  4.     Clear()
  5.     Size() int
  6.     Empty() bool
  7.     Push(node INode)
  8.     Poll() (bool, INode)
  9. }

tNode.go

顶点, 实现INode

  1. package bellman_fold
  3. import "fmt"
  5. type tNode struct {
  6.     id string
  7.     weight int
  8. }
  10. func NewNode(id string) INode {
  11.     return &tNode{
  12.         id,MaxWeight,
  13.     }
  14. }
  16. func (me *tNode) ID() string {
  17.     return me.id
  18. }
  20. func (me *tNode) GetWeight() int {
  21.     return me.weight
  22. }
  24. func (me *tNode) SetWeight(w int) {
  25.     me.weight = w
  26. }
  28. func (me *tNode) String() string {
  29.     return fmt.Sprintf("%s(%v)", me.id, me.weight)
  30. }

tLine.go

边, 实现ILine

  1. package bellman_fold
  3. type tLine struct {
  4.     from string
  5.     to string
  6.     weight int
  7. }
  9. func NewLine(from string, to string, weight int) ILine {
  10.     return &tLine{
  11.         from,to,weight,
  12.     }
  13. }
  15. func (me *tLine) From() string {
  16.     return me.from
  17. }
  19. func (me *tLine) To() string {
  20.     return me.to
  21. }
  23. func (me *tLine) Weight() int {
  24.     return me.weight
  25. }

tFIFOQueue.go

FIFO节点队列的实现

  1. package bellman_fold
  3. type tFIFOQueue struct {
  4.     nodes []INode
  5.     capacity int
  6.     rindex int
  7.     windex int
  8. }
  10. func newFIFOQueue() iNodeQueue {
  11.     it := &tFIFOQueue{}
  12.     it.Clear()
  13.     return it
  14. }
  16. func (me *tFIFOQueue) Clear() {
  17.     me.nodes = make([]INode, 0)
  18.     me.capacity = 0
  19.     me.rindex = -1
  20.     me.windex = -1
  21. }
  23. func (me *tFIFOQueue) Size() int {
  24.     return me.windex - me.rindex
  25. }
  27. func (me *tFIFOQueue) Empty() bool {
  28.     return me.Size() <= 0
  29. }
  31. func (me *tFIFOQueue) Push(node INode) {
  32.     me.ensureSpace(1)
  33.     me.windex++
  34.     me.nodes[me.windex] = node
  35. }
  37. func (me *tFIFOQueue) ensureSpace(size int) {
  38.     for me.capacity < me.windex + size + 1 {
  39.         me.nodes = append(me.nodes, nil)
  40.         me.capacity++
  41.     }
  42. }
  44. func (me *tFIFOQueue) Poll() (bool, INode) {
  45.     if me.Empty() {
  46.         return false, nil
  47.     }
  49.     me.rindex++
  50.     it := me.nodes[me.rindex]
  51.     me.nodes[me.rindex] = nil
  53.     if me.rindex > me.capacity / 2 {
  54.         size := me.Size()
  55.         offset := me.rindex + 1
  56.         for i := 0;i < size;i++ {
  57.             me.nodes[i], me.nodes[i + offset] = me.nodes[i + offset], nil
  58.         }
  60.         me.rindex -= offset
  61.         me.windex -= offset
  62.     }
  64.     return true, it
  65. }

tBellmanFoldFinder.go

贝尔曼-福特算法的实现

  1. package bellman_fold
  3. type tBellmanFoldFinder struct {
  4. }
  7. func newBellmanFoldFinder() IPathFinder {
  8.     return &tBellmanFoldFinder{
  9.     }
  10. }
  12. func (me *tBellmanFoldFinder) FindPath(nodes []INode, lines []ILine, fromID string, toID string) (bool,[]INode) {
  13.     // 节点索引
  14.     mapNodes := make(map[string]INode, 0)
  15.     for _,it := range nodes {
  16.         mapNodes[it.ID()] = it
  17.     }
  19.     fromNode, ok := mapNodes[fromID]
  20.     if !ok {
  21.         return false, nil
  22.     }
  24.     toNode,ok := mapNodes[toID]
  25.     if !ok {
  26.         return false, nil
  27.     }
  29.     // 边的索引
  30.     mapFromLines := make(map[string][]ILine, 0)
  31.     mapToLines := make(map[string][]ILine, 0)
  32.     for _, it := range lines {
  33.         if v,ok := mapFromLines[it.From()];ok {
  34.             mapFromLines[it.From()] = append(v, it)
  35.         } else {
  36.             mapFromLines[it.From()] = []ILine{ it }
  37.         }
  39.         if v,ok := mapToLines[it.To()];ok {
  40.             mapToLines[it.To()] = append(v, it)
  41.         } else {
  42.             mapToLines[it.To()] = []ILine{ it }
  43.         }
  44.     }
  46.     // 设置from节点的weight为0, 其他节点的weight为MaxWeight
  47.     for _,it := range nodes {
  48.         if it.ID() == fromID {
  49.             it.SetWeight(0)
  50.         } else {
  51.             it.SetWeight(MaxWeight)
  52.         }
  53.     }
  55.     // 循环更新所有节点的权重 直到不再变化
  56.     fromNode.SetWeight(0)
  57.     queue := newFIFOQueue()
  58.     queue.Push(fromNode)
  59.     for !queue.Empty() {
  60.         ok,from := queue.Poll()
  61.         if !ok {
  62.             panic("unexpected !ok")
  63.         }
  65.         affectedLines, ok := mapFromLines[from.ID()]
  66.         if ok {
  67.             for _,line := range affectedLines {
  68.                 if to,ok := mapNodes[line.To()];ok {
  69.                     if me.updateWeight(from, to, line) {
  70.                         queue.Push(to)
  71.                     }
  72.                 }
  73.             }
  74.         }
  75.     }
  77.     // 逆向查找最短路径
  78.     if toNode.GetWeight() >= MaxWeight {
  79.         return false, nil
  80.     }
  82.     queue.Clear()
  83.     queue.Push(toNode)
  84.     current := toNode
  85.     maxRound := len(lines)
  86.     for ;current != fromNode && maxRound > 0;maxRound-- {
  87.         linkedLines, _ := mapToLines[current.ID()]
  88.         for _,line := range linkedLines {
  89.             from, _ := mapNodes[line.From()]
  90.             if from.GetWeight() == current.GetWeight() - line.Weight() {
  91.                 current = from
  92.                 queue.Push(from)
  93.             }
  94.         }
  95.     }
  97.     if current != fromNode {
  98.         return false, nil
  99.     }
  101.     // 返回
  102.     result := make([]INode, queue.Size())
  103.     for i := queue.Size() - 1;i >= 0;i-- {
  104.         _,result[i] = queue.Poll()
  105.     }
  106.     return true, result
  107. }
  109. func (me *tBellmanFoldFinder) updateWeight(from INode, to INode, line ILine) bool {
  110.     w := me.min(from.GetWeight() + line.Weight(), to.GetWeight())
  111.     if to.GetWeight() > w {
  112.         to.SetWeight(w)
  113.         return true
  114.     }
  116.     return false
  117. }
  119. func (me *tBellmanFoldFinder) min(a, b int) int {
  120.     if a <= b {
  121.         return a
  122.     }
  123.     return b
  124. }
  126. var BellmanFoldFinder = newBellmanFoldFinder()

(end)