go Dijkstra算法 leetcode 743

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

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

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

655 次点击  ∙  2 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传