缘起

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

狄克斯特拉算法

  1. 与贝尔曼-福特算法类似，
  2. 狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，
  3. 使用它可以求得从起点到终点的路径中权重总和最小的那条路径。
  5. 比起需要对所有的边都重复计算权重和更新权重的贝尔曼-福特算法，
  6. 狄克斯特拉算法多了一步选择顶点的操作，
  7. 这使得它在求最短路径上更为高效。
  9. 如果闭环中有负数权重，就不存在最短路径。
  10. 贝尔曼-福特算法可以直接认定不存在最短路径，
  11. 但在狄克斯特拉算法中，即便不存在最短路径，
  12. 它也会算出一个错误的最短路径出来。
  13. 因此，有负数权重时不能使用狄克斯特拉算法。
  15. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一
  • 狄克斯特拉算法与贝尔曼-福特算法非常相似, 主要区别在于总是优先选择权重最小的候选节点.
  • 因此, 贝尔曼-福特算法使用队列或堆栈存储候选节点, 而狄克斯特拉算法使用堆.

    流程

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

设计

  • INode: 顶点接口
  • ILine: 边接口
  • IPathFinder: 最短路径查找算法接口
  • IComparator: 顶点比较接口
  • IHeap: 顶点堆接口
  • tNode: 顶点, 实现INode
  • tLine: 边, 实现ILine
  • tNodeWeightComparator: 基于权重的顶点比较器, 实现IComparator接口
  • tArrayHeap: 堆的实现
  • tDijkstraPathFinder: 狄克斯特拉算法的实现

单元测试

dijkstra_finder_test.go

  1. package graph
  3. import (
  4.     "fmt"
  5.     dk "learning/gooop/graph/dijkstra"
  6.     "strings"
  7.     "testing"
  8. )
  10. func Test_DijkstraFinder(t *testing.T) {
  11.     fnAssertTrue := func(b bool, msg string) {
  12.         if !b {
  13.             t.Fatal(msg)
  14.         }
  15.     }
  17.     nodes := []dk.INode{
  18.         dk.NewNode("a"),
  19.         dk.NewNode("b"),
  20.         dk.NewNode("c"),
  21.         dk.NewNode("d"),
  22.         dk.NewNode("e"),
  23.         dk.NewNode("f"),
  24.         dk.NewNode("g"),
  25.     }
  27.     lines := []dk.ILine {
  28.         dk.NewLine("a", "b", 9),
  29.         dk.NewLine("a", "c", 2),
  31.         dk.NewLine("b", "c", 6),
  32.         dk.NewLine("b", "d", 3),
  33.         dk.NewLine("b", "e", 1),
  35.         dk.NewLine("c", "d", 2),
  36.         dk.NewLine("c", "f", 9),
  38.         dk.NewLine("d", "e", 5),
  39.         dk.NewLine("d", "f", 6),
  41.         dk.NewLine("e", "f", 3),
  42.         dk.NewLine("e", "g", 7),
  44.         dk.NewLine("f", "g", 4),
  45.     }
  47.     for _,it := range lines[:] {
  48.         lines = append(lines, dk.NewLine(it.To(), it.From(), it.Weight()))
  49.     }
  51.     ok,path := dk.DijkstraPathFinder.FindPath(nodes, lines, "a", "g")
  52.     if !ok {
  53.         t.Fatal("failed to find min path")
  54.     }
  55.     fnPathToString := func(nodes []dk.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.     t.Log(pathString)
  64.     fnAssertTrue(pathString == "a(0) c(2) d(4) f(10) g(14)", "incorrect path")
  65. }

测试输出

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

INode.go

顶点接口

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

ILine.go

边接口

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

IPathFinder.go

最短路径查找算法接口

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

IComparator.go

顶点比较接口

  1. package dijkstra
  3. type IComparator interface {
  4.     Less(a interface{}, b interface{}) bool
  5. }

IHeap.go

顶点堆接口

  1. package dijkstra
  3. type IHeap interface {
  4.     Size() int
  5.     IsEmpty() bool
  6.     IsNotEmpty() bool
  8.     Push(node interface{})
  9.     Pop() (bool, interface{})
  11.     IndexOf(node interface{}) int
  12.     ShiftUp(i int)
  13. }

tNode.go

顶点, 实现INode

  1. package dijkstra
  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 dijkstra
  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. }

tNodeWeightComparator.go

基于权重的顶点比较器, 实现IComparator接口

  1. package dijkstra
  3. import "errors"
  6. type tNodeWeightComparator struct {
  7. }
  9. func newNodeWeightComparator() IComparator {
  10.     return &tNodeWeightComparator{
  11.     }
  12. }
  14. func (me *tNodeWeightComparator) Less(a interface{}, b interface{}) bool {
  15.     if a == nil || b == nil {
  16.         panic(gNullArgumentError)
  17.     }
  19.     n1 := a.(INode)
  20.     n2 := b.(INode)
  21.     return n1.GetWeight() <= n2.GetWeight()
  22. }
  24. var gNullArgumentError = errors.New("null argument error")

tArrayHeap.go

堆的实现

  1. package dijkstra
  3. import (
  4.     "errors"
  5.     "fmt"
  6.     "strings"
  7. )
  9. type tArrayHeap struct {
  10.     comparator IComparator
  11.     items []interface{}
  12.     size int
  13.     version int64
  14. }
  16. func newArrayHeap(comparator IComparator) IHeap {
  17.     return &tArrayHeap{
  18.         comparator: comparator,
  19.         items: make([]interface{}, 0),
  20.         size: 0,
  21.         version: 0,
  22.     }
  23. }
  25. func (me *tArrayHeap) Size() int {
  26.     return me.size
  27. }
  29. func (me *tArrayHeap) IsEmpty() bool {
  30.     return me.size <= 0
  31. }
  33. func (me *tArrayHeap) IsNotEmpty() bool {
  34.     return !me.IsEmpty()
  35. }
  37. func (me *tArrayHeap) Push(value interface{}) {
  38.     me.version++
  40.     me.ensureSize(me.size + 1)
  41.     me.items[me.size] = value
  42.     me.size++
  44.     me.ShiftUp(me.size - 1)
  45.     me.version++
  46. }
  49. func (me *tArrayHeap) ensureSize(size int) {
  50.     for ;len(me.items) < size; {
  51.         me.items = append(me.items, nil)
  52.     }
  53. }
  55. func (me *tArrayHeap) parentOf(i int) int {
  56.     return (i - 1) / 2
  57. }
  59. func (me *tArrayHeap) leftChildOf(i int) int {
  60.     return i*2 + 1
  61. }
  63. func (me *tArrayHeap) rightChildOf(i int) int {
  64.     return me.leftChildOf(i) + 1
  65. }
  67. func (me *tArrayHeap) last() (i int, v interface{}) {
  68.     if me.IsEmpty() {
  69.         return -1, nil
  70.     }
  72.     i = me.size - 1
  73.     v = me.items[i]
  74.     return i,v
  75. }
  77. func (me *tArrayHeap) IndexOf(node interface{}) int {
  78.     n := -1
  79.     for i,it := range me.items {
  80.         if it == node {
  81.             n = i
  82.             break
  83.         }
  84.     }
  86.     return n
  87. }
  89. func (me *tArrayHeap) ShiftUp(i int) {
  90.     if i <= 0 {
  91.         return
  92.     }
  93.     v := me.items[i]
  95.     pi := me.parentOf(i)
  96.     pv := me.items[pi]
  98.     if me.comparator.Less(v, pv) {
  99.         me.items[pi], me.items[i] = v, pv
  100.         me.ShiftUp(pi)
  101.     }
  102. }
  104. func (me *tArrayHeap) Pop() (bool, interface{}) {
  105.     if me.IsEmpty() {
  106.         return false, nil
  107.     }
  109.     me.version++
  111.     top := me.items[0]
  112.     li, lv := me.last()
  113.     me.items[0] = nil
  114.     me.size--
  116.     if me.IsEmpty() {
  117.         return true, top
  118.     }
  120.     me.items[0] = lv
  121.     me.items[li] = nil
  123.     me.shiftDown(0)
  124.     me.version++
  126.     return true, top
  127. }
  129. func (me *tArrayHeap) shiftDown(i int) {
  130.     pv := me.items[i]
  131.     ok, ci, cv := me.minChildOf(i)
  132.     if ok && me.comparator.Less(cv, pv) {
  133.         me.items[i], me.items[ci] = cv, pv
  134.         me.shiftDown(ci)
  135.     }
  136. }
  138. func (me *tArrayHeap) minChildOf(p int) (ok bool, i int, v interface{}) {
  139.     li := me.leftChildOf(p)
  140.     if li >= me.size {
  141.         return false, 0, nil
  142.     }
  143.     lv := me.items[li]
  145.     ri := me.rightChildOf(p)
  146.     if ri >= me.size {
  147.         return true, li, lv
  148.     }
  149.     rv := me.items[ri]
  151.     if me.comparator.Less(lv, rv) {
  152.         return true, li, lv
  153.     } else {
  154.         return true, ri, rv
  155.     }
  156. }
  158. func (me *tArrayHeap) String() string {
  159.     level := 0
  160.     lines := make([]string, 0)
  161.     lines = append(lines, "")
  163.     for {
  164.         n := 1<<level
  165.         min := n - 1
  166.         max := n + min - 1
  167.         if min >= me.size {
  168.             break
  169.         }
  171.         line := make([]string, 0)
  172.         for i := min;i <= max;i++ {
  173.             if i >= me.size {
  174.                 break
  175.             }
  176.             line = append(line, fmt.Sprintf("%4d", me.items[i]))
  177.         }
  178.         lines = append(lines, strings.Join(line, ","))
  180.         level++
  181.     }
  183.     return strings.Join(lines, "\n")
  184. }
  186. var gNoMoreElementsError = errors.New("no more elements")

tDijkstraPathFinder.go

狄克斯特拉算法的实现

  1. package dijkstra
  3. type tDijkstraPathFinder struct {
  4. }
  6. func newDijkstraPathFinder() IPathFinder {
  7.     return &tDijkstraPathFinder{}
  8. }
  10. func (me *tDijkstraPathFinder) FindPath(nodes []INode, lines []ILine, srcID string, dstID string) (bool,[]INode) {
  11.     // 节点索引
  12.     mapNodes := make(map[string]INode, 0)
  13.     for _,it := range nodes {
  14.         mapNodes[it.ID()] = it
  15.     }
  17.     srcNode, ok := mapNodes[srcID]
  18.     if !ok {
  19.         return false, nil
  20.     }
  22.     dstNode,ok := mapNodes[dstID]
  23.     if !ok {
  24.         return false, nil
  25.     }
  27.     // 边的索引
  28.     mapFromLines := make(map[string][]ILine, 0)
  29.     mapToLines := make(map[string][]ILine, 0)
  30.     for _, it := range lines {
  31.         if v,ok := mapFromLines[it.From()];ok {
  32.             mapFromLines[it.From()] = append(v, it)
  33.         } else {
  34.             mapFromLines[it.From()] = []ILine{ it }
  35.         }
  37.         if v,ok := mapToLines[it.To()];ok {
  38.             mapToLines[it.To()] = append(v, it)
  39.         } else {
  40.             mapToLines[it.To()] = []ILine{ it }
  41.         }
  42.     }
  44.     // 设置from节点的weight为0, 其他节点的weight为MaxWeight
  45.     for _,it := range nodes {
  46.         if it.ID() == srcID {
  47.             it.SetWeight(0)
  48.         } else {
  49.             it.SetWeight(MaxWeight)
  50.         }
  51.     }
  53.     // 将起点push到堆
  54.     heap := newArrayHeap(newNodeWeightComparator())
  55.     heap.Push(srcNode)
  57.     // 遍历候选节点
  58.     for heap.IsNotEmpty() {
  59.         _, top := heap.Pop()
  60.         from := top.(INode)
  61.         if from.ID() == dstID {
  62.             break
  63.         }
  65.         links, ok := mapFromLines[from.ID()]
  66.         if ok {
  67.             for _,line := range links {
  68.                 if to,ok := mapNodes[line.To()];ok {
  69.                     if me.updateWeight(from, to, line) {
  70.                         n := heap.IndexOf(to)
  71.                         if n >= 0 {
  72.                             heap.ShiftUp(n)
  73.                         } else {
  74.                             heap.Push(to)
  75.                         }
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.     }
  82.     // 逆向查找最短路径
  83.     if dstNode.GetWeight() >= MaxWeight {
  84.         return false, nil
  85.     }
  87.     path := []INode{ dstNode }
  88.     current := dstNode
  89.     maxRound := len(lines)
  90.     for ;current != srcNode && maxRound > 0;maxRound-- {
  91.         linkedLines, _ := mapToLines[current.ID()]
  92.         for _,line := range linkedLines {
  93.             from, _ := mapNodes[line.From()]
  94.             if from.GetWeight() == current.GetWeight() - line.Weight() {
  95.                 current = from
  96.                 path = append(path, from)
  97.             }
  98.         }
  99.     }
  101.     if current != srcNode {
  102.         return false, nil
  103.     }
  105.     me.reverse(path)
  106.     return true, path
  107. }
  110. func (me *tDijkstraPathFinder) reverse(nodes []INode) {
  111.     for i,j := 0, len(nodes)-1;i < j;i,j=i+1,j-1 {
  112.         nodes[i], nodes[j] = nodes[j], nodes[i]
  113.     }
  114. }
  116. func (me *tDijkstraPathFinder) updateWeight(from INode, to INode, line ILine) bool {
  117.     w := me.min(from.GetWeight() + line.Weight(), to.GetWeight())
  118.     if to.GetWeight() > w {
  119.         to.SetWeight(w)
  120.         return true
  121.     }
  123.     return false
  124. }
  127. func (me *tDijkstraPathFinder) min(a, b int) int {
  128.     if a <= b {
  129.         return a
  130.     }
  131.     return b
  132. }
  135. var DijkstraPathFinder = newDijkstraPathFinder()

(end)