手?jǐn)]golang 基本數(shù)據(jù)結(jié)構(gòu)與算法 圖的最短路徑 　狄克斯特拉算法

緣起

最近閱讀<<我的第一本算法書>>(【日】石田保輝；宮崎修一)
本系列筆記擬采用golang練習(xí)之

狄克斯特拉算法

與貝爾曼-福特算法類似，
狄克斯特拉（Dijkstra）算法也是求解最短路徑問題的算法，
使用它可以求得從起點(diǎn)到終點(diǎn)的路徑中權(quán)重總和最小的那條路徑。

比起需要對(duì)所有的邊都重復(fù)計(jì)算權(quán)重和更新權(quán)重的貝爾曼-福特算法，
狄克斯特拉算法多了一步選擇頂點(diǎn)的操作，
這使得它在求最短路徑上更為高效。

如果閉環(huán)中有負(fù)數(shù)權(quán)重，就不存在最短路徑。
貝爾曼-福特算法可以直接認(rèn)定不存在最短路徑，
但在狄克斯特拉算法中，即便不存在最短路徑，
它也會(huì)算出一個(gè)錯(cuò)誤的最短路徑出來。
因此，有負(fù)數(shù)權(quán)重時(shí)不能使用狄克斯特拉算法。

摘自 <<我的第一本算法書>> 【日】石田保輝；宮崎修一
  • 狄克斯特拉算法與貝爾曼-福特算法非常相似, 主要區(qū)別在于總是優(yōu)先選擇權(quán)重最小的候選節(jié)點(diǎn).
  • 因此, 貝爾曼-福特算法使用隊(duì)列或堆棧存儲(chǔ)候選節(jié)點(diǎn), 而狄克斯特拉算法使用堆.

流程

  1. 給定若干頂點(diǎn), 以及頂點(diǎn)間的若干條邊, 尋找從指定起點(diǎn)srcNode到指定終點(diǎn)dstNode的最小權(quán)重路徑
  2. 設(shè)定srcNode的權(quán)重為0, 其他頂點(diǎn)的權(quán)重為無窮大
  3. 將srcNode節(jié)點(diǎn)送入候選堆
  4. for 候選堆不為空:
    1. 從候選堆pop頂點(diǎn)node
    2. 如果node.id == dstNode.id, 循環(huán)結(jié)束
    3. 遍歷從node出發(fā)的所有邊, 將邊的終點(diǎn)to的權(quán)重, 更新為min(終點(diǎn)權(quán)重, node.權(quán)重+邊.權(quán)重)
    4. 如果to.權(quán)重 > node.權(quán)重+邊.權(quán)重, 說明更新有效
    5. 如果更新有效, 判斷to是否在堆中, 如果是, 則上浮以維護(hù)堆秩序, 否則, 將to節(jié)點(diǎn)push入候選堆
  5. 判斷終點(diǎn)的權(quán)重是否被更新(!=無窮大), 如果是則說明存在最短路徑
  6. 反向查找最短路徑:
    1. 設(shè)定當(dāng)前節(jié)點(diǎn)current = 終點(diǎn)
    2. push節(jié)點(diǎn)current進(jìn)路徑隊(duì)列
    3. 遍歷終點(diǎn)為current的邊, 查找符合條件的node:邊的起點(diǎn).權(quán)重 = current.權(quán)重-邊.權(quán)重
    4. push節(jié)點(diǎn)node進(jìn)路徑隊(duì)列
    5. 循環(huán)1-4, 直到current == srcNode, 查找完成

設(shè)計(jì)

  • INode: 頂點(diǎn)接口
  • ILine: 邊接口
  • IPathFinder: 最短路徑查找算法接口
  • IComparator: 頂點(diǎn)比較接口
  • IHeap: 頂點(diǎn)堆接口
  • tNode: 頂點(diǎn), 實(shí)現(xiàn)INode
  • tLine: 邊, 實(shí)現(xiàn)ILine
  • tNodeWeightComparator: 基于權(quán)重的頂點(diǎn)比較器, 實(shí)現(xiàn)IComparator接口
  • tArrayHeap: 堆的實(shí)現(xiàn)
  • tDijkstraPathFinder: 狄克斯特拉算法的實(shí)現(xiàn)

單元測試

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

頂點(diǎn)接口

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

頂點(diǎn)比較接口

package dijkstra

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

IHeap.go

頂點(diǎn)堆接口

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

頂點(diǎn), 實(shí)現(xiàn)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

邊, 實(shí)現(xiàn)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

基于權(quán)重的頂點(diǎn)比較器, 實(shí)現(xiàn)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

堆的實(shí)現(xiàn)

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

狄克斯特拉算法的實(shí)現(xiàn)

package dijkstra

type tDijkstraPathFinder struct {
}

func newDijkstraPathFinder() IPathFinder {
    return &tDijkstraPathFinder{}
}

func (me *tDijkstraPathFinder) FindPath(nodes []INode, lines []ILine, srcID string, dstID string) (bool,[]INode) {
    // 節(jié)點(diǎn)索引
    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 }
        }
    }

    // 設(shè)置from節(jié)點(diǎn)的weight為0, 其他節(jié)點(diǎn)的weight為MaxWeight
    for _,it := range nodes {
        if it.ID() == srcID {
            it.SetWeight(0)
        } else {
            it.SetWeight(MaxWeight)
        }
    }

    // 將起點(diǎn)push到堆
    heap := newArrayHeap(newNodeWeightComparator())
    heap.Push(srcNode)

    // 遍歷候選節(jié)點(diǎn)
    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)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容