LeetCode-743

题目

743. 网络延迟时间

结果

代码

数据结构、离散数学、计算机网络、算法每次都学一遍的迪杰斯特拉算法

const INFINITY = math.MaxInt64

func networkDelayTime(times [][]int, n int, k int) int {
	D := make(map[int]int)  // shortest path from k to other nodes
	S := make(map[int]bool) // nodes whose shortest path is already calculated

	// initialize
	for i := 1; i <= n; i++ {
		D[i] = INFINITY
	}
	D[k] = 0
	DISTANCE := make(map[string]int)
	for _, edge := range times {
		DISTANCE[strconv.Itoa(edge[0])+" "+strconv.Itoa(edge[1])] = edge[2]
	}

	for {
		// the nearest node to source node which is not in set S
		u := extractMin(D, S)
		if u == -1 {
			break
		}
		S[u] = true
		for v, dist := range D {
			if _, ok := S[v]; !ok {
				uv := edge(u, v, DISTANCE)
				if uv != -1 {
					if D[u]+uv < dist {
						D[v] = D[u] + uv
					}
				}
			}
		}
	}

	max := -1
	for _, distance := range D {
		if distance == INFINITY {
			return -1
		}
		if distance > max && distance != 0 {
			max = distance
		}
	}
	return max
}

// distance from u to v, if there is no path, return -1
func edge(u, v int, distance map[string]int) int {
	d, ok := distance[strconv.Itoa(u)+" "+strconv.Itoa(v)]
	if !ok {
		return -1
	}
	return d
}

// the nearest node to source node which is not in set S, if not found, return -1
func extractMin(D map[int]int, S map[int]bool) int {
	minDistance := INFINITY
	ans := -1
	for node, distance := range D {
		if _, ok := S[node]; !ok {
			if distance < minDistance {
				ans = node
				minDistance = distance
			}
		}
	}
	return ans
}