缘起
最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之
狄克斯特拉算法
与贝尔曼-福特算法类似，
狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，
使用它可以求得从起点到终点的路径中权重总和最小的那条路径。
比起需要对所有的边都重复计算权重和更新权重的贝尔曼-福特算法，
狄克斯特拉算法多了一步选择顶点的操作，
这使得它在求最短路径上更为高效。
如果闭环中有负数权重，就不存在最短路径。
贝尔曼-福特算法可以直接认定不存在最短路径，
但在狄克斯特拉算法中，即便不存在最短路径，
它也会算出一个错误的最短路径出来。
因此，有负数权重时不能使用狄克斯特拉算法。
摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一
- 狄克斯特拉算法与贝尔曼-福特算法非常相似, 主要区别在于总是优先选择权重最小的候选节点.
- 因此, 贝尔曼-福特算法使用队列或堆栈存储候选节点, 而狄克斯特拉算法使用堆.
流程
- 给定若干顶点, 以及顶点间的若干条边, 寻找从指定起点srcNode到指定终点dstNode的最小权重路径
- 设定srcNode的权重为0, 其他顶点的权重为无穷大
- 将srcNode节点送入候选堆
- for 候选堆不为空:
- 从候选堆pop顶点node
- 如果node.id == dstNode.id, 循环结束
- 遍历从node出发的所有边, 将边的终点to的权重, 更新为min(终点权重, node.权重+边.权重)
- 如果to.权重 > node.权重+边.权重, 说明更新有效
- 如果更新有效, 判断to是否在堆中, 如果是, 则上浮以维护堆秩序, 否则, 将to节点push入候选堆
- 判断终点的权重是否被更新(!=无穷大), 如果是则说明存在最短路径
- 反向查找最短路径:
- 设定当前节点current = 终点
- push节点current进路径队列
- 遍历终点为current的边, 查找符合条件的node:边的起点.权重 = current.权重-边.权重
- push节点node进路径队列
- 循环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)
