# go Dijkstra算法 leetcode 743

letterbeezps · · 1364 次点击 · · 开始浏览

# 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 } ```

0 回复

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