LeetCode 743. 网络延迟时间

Categories:

题目描述
思路分析
1. 解法一：Dijkstra 最短路（推荐）
相似题目

题目描述

✅ 743. 网络延迟时间

思路分析

解法一：Dijkstra 最短路（推荐）

核心思路：

使用邻接表表示有向带权图。

用优先队列维护当前可扩展的最小距离节点。

当所有节点都可达时，答案为最短路中的最大值。

复杂度分析：

时间复杂度：O(E log V)，其中 V 表示节点数，E 表示边数。

空间复杂度：O(E + V)，用于图结构与堆。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] graph = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] t : times) {
            graph[t[0]].add(new int[] {t[1], t[2]});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[] {0, k});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0];
            int node = cur[1];

            if (d > dist[node]) {
                continue;
            }

            for (int[] edge : graph[node]) {
                int next = edge[0];
                int w = edge[1];
                if (dist[node] + w < dist[next]) {
                    dist[next] = dist[node] + w;
                    pq.offer(new int[] {dist[next], next});
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }

        return ans;
    }
}

import "container/heap"

type Edge struct {
	to   int
	cost int
}

type Item struct {
	node int
	dist int
}

type MinHeap []Item

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func networkDelayTime(times [][]int, n int, k int) int {
	graph := make([][]Edge, n+1)
	for _, t := range times {
		graph[t[0]] = append(graph[t[0]], Edge{to: t[1], cost: t[2]})
	}

	const inf = int(1 << 60)
	dist := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dist[i] = inf
	}
	dist[k] = 0

	h := &MinHeap{}
	heap.Init(h)
	heap.Push(h, Item{node: k, dist: 0})

	for h.Len() > 0 {
		cur := heap.Pop(h).(Item)
		if cur.dist > dist[cur.node] {
			continue
		}
		for _, e := range graph[cur.node] {
			nd := cur.dist + e.cost
			if nd < dist[e.to] {
				dist[e.to] = nd
				heap.Push(h, Item{node: e.to, dist: nd})
			}
		}
	}

	ans := 0
	for i := 1; i <= n; i++ {
		if dist[i] == inf {
			return -1
		}
		if dist[i] > ans {
			ans = dist[i]
		}
	}

	return ans
}

相似题目

题目	难度	考察点
787. K 站中转内最便宜的航班	中等	最短路
1514. 概率最大的路径	中等	最短路
1334. 阈值距离内邻居最少的城市	中等	最短路
127. 单词接龙	困难	BFS
1631. 最小体力消耗路径	中等	最短路

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/24042204