LeetCode 补充题 191. 带权有向图中两点间的最短距离

2026-09-14 HGNULB 约 6 分钟

文章信息 2 个分类 5 个标签

分类

补充题中等

题目描述

[!green]

牛客原题： ✅ 补充题 191. 带权有向图中两点间的最短距离

给定非负权有向图，节点编号为 1 到 n，边列表 times 每项为 [起点,终点,权重]。

返回从 1 到 n 的最短距离，不可达返回 -1。

示例 1：

输入： n = 3, times = [[1,2,2],[2,3,3],[1,3,8]]
输出： 5

提示：

1 <= n <= 10000
0 <= 权重 <= 1000
允许重边。

题意分析

目标仅是从 1 到 n 的最短距离，不要求起点能到达所有节点。边有方向且权重非负，适合用最小堆按当前距离扩展；重边分别参与松弛即可。

解法：Dijkstra

核心思路

[!blue]

dist[v] 保存当前找到的从 1 到 v 的最短距离，堆中保存待处理的“距离、节点”候选。起点距离为 0，其余设为无穷大。

每次取堆中距离最小的候选。因为边权非负，绕经更远候选不会把这个最小距离再缩短；于是扫描它的有向出边，若 dist[u]+w 小于 dist[v]，就更新 v 并放入新候选。

同一节点可能有旧记录残留在堆里。出堆距离大于当前 dist 时跳过，避免反复处理已被更优路径替代的状态。最后只读取 dist[n]，不能因为无关节点不可达就返回 -1。

解题步骤

按起点建立邻接表，仅保存输入规定方向的边。

令 dist[1] 为 0，其余距离为无穷大，将起点加入最小堆。

弹出候选，跳过已经被更短距离替代的旧记录，并用当前距离松弛各条出边。

堆处理结束后，dist[n] 仍为无穷大则返回 -1，否则返回该距离。

代码实现

class Solution {
    public int shortestPath(int[][] times, int n) {
        int k = 1;
        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
                    });
                }
            }
        }

        return dist[n] == Integer.MAX_VALUE ? -1 : dist[n];
    }
}

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 any) {
    *h = append(*h, x.(Item))
}

func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

func shortestPath(times [][]int, n int) int {
    k := 1
    graph := make([][]Edge, n+1)
    for _, t := range times {
        graph[t[0]] = append(graph[t[0]], Edge{to: t[1], cost: t[2]})
    }
    inf := n*1000 + 1
    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})
            }
        }
    }

    if dist[n] == inf {
        return -1
    }
    return dist[n]
}

复杂度分析

时间复杂度：$O((n+m)\log(m+2))$。

空间复杂度：$O(n+m)$。

关键点总结

[!green]

从 1 号节点运行 Dijkstra，用最小堆取当前最短候选并松弛有向出边；最终只读取 dist[n]，不要求其余节点可达。

易错点总结

[!yellow]

边权允许为 0；Dijkstra 依赖非负边权，不要求严格为正。

有向边不能额外加入反向边，重边也不能随意覆盖。

无穷大必须大于合法最短距离。边权上限为 1000，非负图总能选取不含环的最短路，因此 n×1000+1 足够。

堆中的旧距离不会自动删除，出堆后需要检查是否过期。

相似题目

题目	难度	关联与区别
743. 网络延迟时间	中等	都可用 Dijkstra 求非负边权有向图最短路；该题返回源点到所有节点距离的最大值，本题只查询 1 到 n，其他节点不可达不影响答案。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/849179562712

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！