4
go Dijkstra算法 leetcode 743
source link: https://studygolang.com/articles/35635
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
go Dijkstra算法
Dijkstra算法可以计算带权图上某个点k,到其他点的最短路径,思路是bfs,全局维护一个distance表,distance[i] 表示节点k到节点 i 的最短路径,,每次bfs的起点是j,distance[j] = min(distance),直到bfs结束,为了每次找bfs的起点j,还需要用上优先队列
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
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK