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

ioly · · 1153 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

缘起

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

有疑问加站长微信联系（非本文作者）

本文来自：Segmentfault

感谢作者：ioly

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

入群交流（和以上内容无关）：加入Go大咖交流群，或添加微信：liuxiaoyan-s 备注：入群；或加QQ群：692541889

1153 次点击

加入收藏微博

收入我的专栏

上一篇：go mod 使用

下一篇：高并发系统的限流策略：漏桶和令牌桶(附源码剖析)

测试

顶点的权

符合条件

权重

0 回复

添加一条新回复（您需要登录后才能回复没有账号？）

请尽量让自己的回复能够对别人有帮助
支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
图片支持拖拽、截图粘贴等方式上传

关注我

扫码关注领全套学习资料
加入 QQ 群：
- 192706294（已满）
- 731990104（已满）
- 798786647（已满）
- 729884609（已满）
- 977810755（已满）
- 815126783（已满）
- 812540095（已满）
- 1006366459（已满）
- 692541889
加入微信群：liuxiaoyan-s，备注入群
也欢迎加入知识星球 Go粉丝们（免费）

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

缘起

狄克斯特拉算法

流程

设计

单元测试

测试输出

INode.go

ILine.go

IPathFinder.go

IComparator.go

IHeap.go

tNode.go

tLine.go

tNodeWeightComparator.go

tArrayHeap.go

tDijkstraPathFinder.go

用户登录

今日阅读排行

一周阅读排行

关注我

缘起

狄克斯特拉算法

流程

设计

单元测试

测试输出

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

用户登录

今日阅读排行

一周阅读排行

关注我

给该专栏投稿 写篇新文章

收入到我管理的专栏 新建专栏

缘起

狄克斯特拉算法

流程

设计

单元测试

测试输出

INode.go

ILine.go

IPathFinder.go

IComparator.go

IHeap.go

tNode.go

tLine.go

tNodeWeightComparator.go

tArrayHeap.go

tDijkstraPathFinder.go

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

给该专栏投稿写篇新文章

收入到我管理的专栏新建专栏