# go Dijkstra算法
Dijkstra算法可以计算带权图上某个点k，到其他点的最短路径，思路是bfs，全局维护一个distance表，distance[i] 表示节点k到节点 i 的最短路径，，每次bfs的起点是j，distance[j] = min(distance)，直到bfs结束，为了每次找bfs的起点j，还需要用上[优先队列](https://studygolang.com/articles/35556)
## code
```go
package main
import "container/heap"
// items [[2,1,1],[2,3,1],[3,4,1]] [u, v, w] 表示节点u于v相邻，且权重为w
func dijkstra(times [][]int, n int, k int) int {
// 构建图，邻接表结构
graph := make(map[int][][]int)
for i := 0; i < len(times); i++ {
graph[times[i][0]] = append(graph[times[i][0]], times[i][1:])
}
// 存储点k到每个节点的最小距离
distince := make(map[int]int)
// fmt.Println(graph)
pq := make(PriorityQueue, 0)
// 起始节点k, k到k的距离为0
heap.Push(&pq, &Item{
value: []int{0, k},
priority: 0,
})
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
dis, node := item.value[0], item.value[1]
if _, ok := distince[node]; ok {
continue
}
distince[node] = dis
for i := 0; i < len(graph[node]); i++ {
nextNode, nextDis := graph[node][i][0], graph[node][i][1]
if _, ok := distince[nextNode]; !ok {
newItem := &Item{
value: []int{nextDis + dis, nextNode},
priority: nextDis + dis,
}
heap.Push(&pq, newItem)
}
}
}
// distance[i]表示节点k到节点i的最短路径
if len(distince) != n {
return -1
} else {
res := -1
for _, v := range distince {
res = max(res, v)
}
return res
}
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
type Item struct {
value []int
priority int
index int
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int {
return len(pq)
}
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 = j
pq[j].index = i
}
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
item.index -= 1
*pq = old[0 : n-1]
return item
}
```
有疑问加站长微信联系（非本文作者））
