关于算法:手撸golang-基本数据结构与算法-图的最短路径-狄克斯特拉算法

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

 与贝尔曼 - 福特算法相似，狄克斯特拉（Dijkstra）算法也是求解最短门路问题的算法，应用它能够求得从终点到起点的门路中权重总和最小的那条门路。比起须要对所有的边都反复计算权重和更新权重的贝尔曼 - 福特算法，狄克斯特拉算法多了一步抉择顶点的操作，这使得它在求最短门路上更为高效。如果闭环中有正数权重，就不存在最短门路。贝尔曼 - 福特算法能够间接认定不存在最短门路，但在狄克斯特拉算法中，即使不存在最短门路，它也会算出一个谬误的最短门路进去。因而，有正数权重时不能应用狄克斯特拉算法。摘自 << 我的第一本算法书 >>【日】石田保辉；宫崎修一

狄克斯特拉算法与贝尔曼 - 福特算法十分类似, 次要区别在于总是优先选择权重最小的候选节点.
因而, 贝尔曼 - 福特算法应用队列或堆栈存储候选节点, 而狄克斯特拉算法应用堆.

给定若干顶点, 以及顶点间的若干条边, 寻找从指定终点 srcNode 到指定起点 dstNode 的最小权重门路
设定 srcNode 的权重为 0, 其余顶点的权重为无穷大
将 srcNode 节点送入候选堆
for 候选堆不为空:
1. 从候选堆 pop 顶点 node
2. 如果 node.id == dstNode.id, 循环完结
3. 遍历从 node 登程的所有边, 将边的起点 to 的权重, 更新为 min(起点权重, node. 权重 + 边. 权重)
4. 如果 to. 权重 > node. 权重 + 边. 权重, 阐明更新无效
5. 如果更新无效, 判断 to 是否在堆中, 如果是, 则上浮以保护堆秩序, 否则, 将 to 节点 push 入候选堆
判断起点的权重是否被更新 (!= 无穷大), 如果是则阐明存在最短门路
反向查找最短门路:
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

package graph

import (
    "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)
PASS
ok      command-line-arguments  0.001s

顶点接口

package dijkstra

type INode interface {ID() string
    GetWeight() int
    SetWeight(int)
}

const MaxWeight = int(0x7fffffff_ffffffff)

边接口

package dijkstra

type ILine interface {From() string
    To() string
    Weight() int}

最短门路查找算法接口

package dijkstra

type IPathFinder interface {FindPath(nodes []INode, lines []ILine, from string, to string) (bool,[]INode)
}

顶点比拟接口

package dijkstra

type IComparator interface {Less(a interface{}, b interface{}) bool
}

顶点堆接口

package dijkstra

type IHeap interface {Size() int
    IsEmpty() bool
    IsNotEmpty() bool

    Push(node interface{})
    Pop() (bool, interface{})

    IndexOf(node interface{}) int
    ShiftUp(i int)
}

顶点, 实现 INode

package dijkstra

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)
}

边, 实现 ILine

package dijkstra

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}

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

package dijkstra

import "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")

堆的实现

package dijkstra

import (
    "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")

狄克斯特拉算法的实现

package dijkstra

type 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)

关于算法:手撸golang-基本数据结构与算法-图的最短路径-狄克斯特拉算法

缘起

狄克斯特拉算法

流程

设计

单元测试

测试输入

INode.go

ILine.go

IPathFinder.go

IComparator.go

IHeap.go

tNode.go

tLine.go

tNodeWeightComparator.go

tArrayHeap.go

tDijkstraPathFinder.go