4

go Dijkstra算法 leetcode 743

 1 year ago
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
}

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK