What is the recommended data structure for this problem pattern?

Use an adjacency matrix for edge management and a min-heap priority queue to implement Dijkstra's algorithm efficiently.

How do I handle shortestPath queries after adding edges?

Run Dijkstra's algorithm from the source node each time, updating only affected paths for efficiency if using a lazy update.

Can this graph support negative edge weights?

No, Dijkstra's algorithm requires non-negative weights. For negative weights, Bellman-Ford would be needed, which increases complexity.

How does the graph handle no path between nodes?

Return -1 whenever shortestPath cannot reach the target node, ensuring correct handling of disconnected nodes.

Is there a limit to how many addEdge or shortestPath calls I can make?

Yes, according to constraints, at most 100 calls are allowed for addEdge and shortestPath each.

#2642

Hard

auto_awesome堆

LeetCode 题解工作台

设计可以求最短路径的图类

给你一个有 n 个节点的有向带权图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [from i , to i , edgeCost i ] 表示从 from i 到 to i 有一条代价为 edgeCost i 的边。请你实现一个 Gra…

图设计堆（优先队列）最短路径

题目描述

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [from_i, to_i, edgeCost_i] 表示从 from_i 到 to_i 有一条代价为 edgeCost_i 的边。

请你实现一个 Graph 类：

Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径最小代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和。

示例 1：

输入：
["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
输出：
[null, 6, -1, null, 6]

解释：
Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // 返回 6 。从 3 到 2 的最短路径如第一幅图所示：3 -> 0 -> 1 -> 2 ，总代价为 3 + 2 + 1 = 6 。
g.shortestPath(0, 3); // 返回 -1 。没有从 0 到 3 的路径。
g.addEdge([1, 3, 4]); // 添加一条节点 1 到节点 3 的边，得到第二幅图。
g.shortestPath(0, 3); // 返回 6 。从 0 到 3 的最短路径为 0 -> 1 -> 3 ，总代价为 2 + 4 = 6 。

提示：

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= from_i, to_i, from, to, node1, node2 <= n - 1
1 <= edgeCost_i, edgeCost <= 10⁶
图中任何时候都不会有重边和自环。
调用 addEdge 至多 100 次。
调用 shortestPath 至多 100 次。

lightbulb

解题思路

方法一：Dijsktra 算法

在初始化函数中，我们先用邻接矩阵 $g$ 存储图的边权，其中 $g_{ij}$ 表示从节点 $i$ 到节点 $j$ 的边权，如果 $i$ 和 $j$ 之间没有边，则 $g_{ij}$ 的值为 $\infty$ 。

在 addEdge 函数中，我们更新 $g_{ij}$ 的值为 $edge[2]$ 。

在 shortestPath 函数中，我们使用 Dijsktra 算法求从节点 $node1$ 到节点 $node2$ 的最短路径，其中 $dist[i]$ 表示从节点 $node1$ 到节点 $i$ 的最短路径， $vis[i]$ 表示节点 $i$ 是否已经被访问过。我们初始化 $dist[node1]$ 为 $0$ ，其余的 $dist[i]$ 均为 $\infty$ 。然后我们遍历 $n$ 次，每次找到当前未被访问过的节点 $t$ ，使得 $dist[t]$ 最小。然后我们将节点 $t$ 标记为已访问，然后更新 $dist[i]$ 的值为 $min(dist[i], dist[t] + g_{ti})$ 。最后我们返回 $dist[node2]$ ，如果 $dist[node2]$ 为 $\infty$ ，则说明从节点 $node1$ 到节点 $node2$ 不存在路径，返回 $-1$ 。

时间复杂度 $O(n^2 \times q)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为节点数，而 $q$ 为 shortestPath 函数的调用次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.g = [[inf] * n for _ in range(n)]
        for f, t, c in edges:
            self.g[f][t] = c

    def addEdge(self, edge: List[int]) -> None:
        f, t, c = edge
        self.g[f][t] = c

    def shortestPath(self, node1: int, node2: int) -> int:
        dist = [inf] * self.n
        dist[node1] = 0
        vis = [False] * self.n
        for _ in range(self.n):
            t = -1
            for j in range(self.n):
                if not vis[j] and (t == -1 or dist[t] > dist[j]):
                    t = j
            vis[t] = True
            for j in range(self.n):
                dist[j] = min(dist[j], dist[t] + self.g[t][j])
        return -1 if dist[node2] == inf else dist[node2]


# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)

speed

复杂度分析

指标	值
时间	complexity per query is O(M + N*V^2 + V^3) considering adjacency updates and Dijkstra runs; space complexity is O(V^2) for the adjacency matrix storing all edge costs.
空间	O(V^2)

psychology

面试官常问的追问

外企场景

question_mark
Checking if you understand dynamic graph updates and how shortest paths can change with new edges.
question_mark
Observing whether you optimize repeated shortest path queries rather than recalculating all paths naively.
question_mark
Evaluating your choice between adjacency list vs adjacency matrix for trade-offs in update vs query speed.

warning

常见陷阱

外企场景

error
Recomputing all shortest paths globally after each edge addition, leading to unnecessary overhead.
error
Using BFS instead of Dijkstra for weighted graphs, resulting in incorrect path costs.
error
Failing to handle the case when no path exists and returning invalid distances instead of -1.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Support undirected weighted graphs with similar dynamic edge additions and shortest path queries.
arrow_right_alt
Allow multiple edges between nodes and compute the shortest path considering only the minimum-cost edge.
arrow_right_alt
Optimize for batch shortest path queries where multiple paths are requested after a sequence of edge additions.

help

常见问题

外企场景

继续练习

#2662 前往目标的最小代价 #2699 修改图中的边权 #2577 在网格图中访问一个格子的最少时间