#2642

Hard

LeetCode Problem Workspace

Design Graph With Shortest Path Calculator

Implement a dynamic weighted directed graph with efficient shortest path queries and edge additions in real time.

graph design heap priority queue shortest path

Problem Statement

Design a weighted directed graph with n nodes numbered from 0 to n - 1. The graph initially contains edges given as edges[i] = [fromi, toi, edgeCosti], representing a direct edge from node fromi to node toi with the associated cost edgeCosti. You need to implement a Graph class capable of handling dynamic edge additions and shortest path queries.

Implement the following operations: addEdge([from, to, cost]) to dynamically add new edges to the graph, and shortestPath(node1, node2) to return the minimum path cost from node1 to node2. If no path exists, return -1. Ensure updates after each edge maintain accurate shortest path calculations even after multiple modifications.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["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]] Output [null, 6, -1, null, 6]

Explanation Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]); g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6. g.shortestPath(0, 3); // return -1. There is no path from 0 to 3. g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above. g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.

Constraints

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= fromi, toi, from, to, node1, node2 <= n - 1
1 <= edgeCosti, edgeCost <= 106
There are no repeated edges and no self-loops in the graph at any point.
At most 100 calls will be made for addEdge.
At most 100 calls will be made for shortestPath.

Solution Approach

Use adjacency matrix for edge management

Maintain a VxV adjacency matrix representing the current edge costs. This allows O(1) access for updates and simplifies recalculating shortest paths after each addEdge call. Initialize the matrix with the given edges and infinity for non-existent edges.

Apply Dijkstra's algorithm with priority queue

For each shortestPath query, run Dijkstra's algorithm from the source node using a min-heap to efficiently select the next closest node. This handles dynamic edge additions well and ensures correct shortest path calculations without recomputing all paths globally.

Update paths incrementally after edge additions

After addEdge updates, only recompute paths affected by the new edge if using a lazy update strategy, or recompute from scratch for guaranteed correctness. This balances time complexity and correctness, especially since edge additions and queries are limited to 100 calls each.

Complexity Analysis

Metric	Value
Time	O(M + N\cdot V^2 + V^3)
Space	O(V^2)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Dijsktra's Algorithm

In the initialization function, we first use the adjacency matrix $g$ to store the edge weights of the graph, where $g_{ij}$ represents the edge weight from node $i$ to node $j$. If there is no edge between $i$ and $j$, the value of $g_{ij}$ is $\infty$.

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

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)

Continue Practicing

#2662 minimum cost of a path with special roads #2699 modify graph edge weights #2577 minimum time to visit a cell in a grid