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

作者: 老罗话编程 | 来源:发表于2021-03-01 08:09 被阅读0次

缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用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

INode.go

顶点接口

package dijkstra

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

const MaxWeight = int(0x7fffffff_ffffffff)

ILine.go

边接口

package dijkstra

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

IPathFinder.go

最短路径查找算法接口

package dijkstra

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

IComparator.go

顶点比较接口

package dijkstra

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

IHeap.go

顶点堆接口

package dijkstra

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

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

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

tNode.go

顶点, 实现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)
}

tLine.go

边, 实现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
}

tNodeWeightComparator.go

基于权重的顶点比较器, 实现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")

tArrayHeap.go

堆的实现

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

tDijkstraPathFinder.go

狄克斯特拉算法的实现

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

设计模式

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

缘起

狄克斯特拉算法

流程

设计

单元测试

测试输出

INode.go

ILine.go

IPathFinder.go

IComparator.go

IHeap.go

tNode.go

tLine.go

tNodeWeightComparator.go

tArrayHeap.go

tDijkstraPathFinder.go

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

设计模式

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