算法-图的最短路径 Dijkstra

图如果不带权重，计算最短路径用BFS，队列的数据结构就够了，如果带权重(负权不能使用dijkstra)的话可以使用优先队列的数据结构。放邻接点的时候，哪个权重小就放到前边。不带权重则是特例。give a think，最好拿笔纸反复练习才好领会这个算法。

最短路径要计算前边累计的，计算好的。

堆 实现优先队列

理解堆排序算法，就很容易理解利用堆来实现优先队列。这里不细说，Go的heap包，内有实现优先队列的例子。

Pop

当从堆中 Pop 一个元素的时候，先把顶点元素和最后一个节点的值交换，然后弹出，再对交换的元素调用 down，向下保证最小堆。

Push

当往堆中 Push 一个元素的时候，这个元素插入到最后一个节点，然后调用 up 函数向上比较。

优先队列代码

heap包实现优先队列的例子ss

import (
  "container/heap"
  "fmt"
)

type Item struct {
  value    string // The value of the item; arbitrary.
  priority int    // The priority of the item in the queue.
  index    int    // The index of the item in the heap.
}

// 利用堆实现优先队列 必须实现sort接口、Push和Pop方法
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// 自己决定priority 大小排位
func (pq PriorityQueue) Less(i, j int) bool {
  return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
  pq[i], pq[j] = pq[j], pq[i]
  pq[i].index = i
  pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
  n := len(*pq)
  item := x.(*Item)
  item.index = n
  *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n-1]
  old[n-1] = nil  // avoid memory leak
  item.index = -1 // for safety
  *pq = old[0 : n-1]
  return item
}

func (pq *PriorityQueue) Trav() {
  for _, x := range *pq {
    fmt.Printf("%#v\n", x)
  }
  fmt.Println()
}

dijkstra算法

package main

import (
  "container/heap"
  "fmt"
  "math"
)

func main() {
  var pq PriorityQueue
  heap.Init(&pq)

  var a = map[string]map[string]int{
    "A": {"B": 5, "C": 1},
    "B": {"A": 5, "C": 2, "D": 1,},
    "C": {"A": 1, "B": 2, "D": 3, "E": 8},
    "D": {"B": 1, "C": 4, "E": 3, "F": 6},
    "E": {"C": 8, "D": 3},
    "F": {"D": 6},
  }

  // 从A点到各个点的最短距离
  parent, distance := dijkstra(a, "A")

  fmt.Println("parent =>", parent)
  fmt.Println("distance =>", distance)

  // 输出到F点的各个点
  v := parent["F"]
  for v != "" {
    fmt.Printf("%s => ", v)
    v = parent[v]
  }

}

// initDistance 初始化距离 默认int最大值即可
func initDistance(g map[string]map[string]int, node string) map[string]int {
  dis := make(map[string]int, len(g))
  for n := range g {
    dis[n] = math.MaxInt64
  }
  dis[node] = 0
  return dis
}

// dijkstra 图g中从node点出发 到其余各点的最短路径，返回路径中各点的父亲和到起始点的距离
func dijkstra(g map[string]map[string]int, node string) (parent map[string]string, dis map[string]int) {
  visited := map[string]bool{
    node: true,
  }
  // 利用优先队列 每次从队列中pop出最短路的节点
  var pq PriorityQueue
  heap.Init(&pq)

  heap.Push(&pq, &Item{
    value:    node,
    priority: 0,
  })

  // 初始化距离
  dis = initDistance(g, node)

  // 各个点的前节点 可以唯一标识一个路径
  parent = make(map[string]string)
  parent[node] = ""

  for pq.Len() > 0 {
    // 优先队列出队
    front := heap.Pop(&pq).(*Item)

    // 取出来才真正算经visited 区别于普通BFS遍历
    visited[front.value] = true
    for v, p := range g[front.value] {
      // 最短距离需要累加前面计算好的距离 如果小于当前dis[v]，则需要变更
      if front.priority+p < dis[v] {
        if !visited[v] {
          heap.Push(&pq, &Item{
            value: v,
            // 优先队列里的权重是累加距离
            priority: front.priority + p,
          })
          // 更新dis和parent
          dis[v] = front.priority + p
          parent[v] = front.value
        }
      }
    }
  }
  return parent, dis
}

参考