There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [fromi, toi, edgeCosti] meaning that there is an edge from fromi to toi with the cost edgeCosti.
Implement the Graph class:
Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.
Example 1:
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 <= 1000 <= edges.length <= n * (n - 1)edges[i].length == edge.length == 30 <= fromi, toi, from, to, node1, node2 <= n - 11 <= edgeCosti, edgeCost <= 106100 calls will be made for addEdge.100 calls will be made for shortestPath.Problem Overview: You need to design a graph data structure that supports two operations: dynamically adding directed weighted edges and computing the shortest path between two nodes. The challenge is balancing update time (addEdge) with query time (shortestPath) while keeping the structure efficient for multiple operations.
Approach 1: Dijkstra's Algorithm with Adjacency List (Time: O((V + E) log V) per query, Space: O(V + E))
Store the graph using an adjacency list where each node keeps a list of (neighbor, weight) pairs. When addEdge is called, append the edge directly to the adjacency list in O(1) time. For shortestPath, run Dijkstra’s algorithm starting from the source node using a min-heap (priority queue). The heap always expands the node with the smallest known distance, ensuring optimal paths in graphs with non‑negative weights. This approach works well when edge additions are frequent but shortest-path queries are moderate. It relies heavily on a heap (priority queue) and classic graph traversal techniques.
Approach 2: Floyd–Warshall Algorithm with Distance Matrix (Time: O(V^3) preprocessing, O(1) query, Space: O(V^2))
Maintain a 2D matrix dist[i][j] representing the shortest distance between every pair of nodes. During initialization, run the Floyd–Warshall algorithm to compute all-pairs shortest paths. Each shortestPath query then becomes a constant-time lookup. When addEdge is called, update the matrix by relaxing paths that could improve using the new edge (u → v). Specifically, iterate over all node pairs and check if going through the new edge shortens their route. This method uses dynamic programming over a shortest path matrix and is ideal when the graph has relatively small n but many queries.
Recommended for interviews: Dijkstra’s algorithm is usually the expected answer. It keeps the design simple, handles dynamic edge additions naturally, and avoids the heavy O(V^3) preprocessing cost. Mentioning Floyd–Warshall shows deeper understanding of all‑pairs shortest path strategies and tradeoffs between preprocessing and query speed.
Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a single source node to all other nodes in a weighted graph with non-negative weights. We can adapt it to efficiently find the shortest path for this problem.
This implementation creates a graph represented as an adjacency matrix and uses the Dijkstra algorithm to find the shortest path between two nodes. The graph is initialized with an empty adjacency matrix and uses an added edge to re-adjust computed paths.
Time Complexity: O(V^2), where V is the number of vertices since we're using an adjacency matrix and no priority queue to obtain the minimum distance vertex.
Space Complexity: O(V^2) due to the adjacency matrix storage requirements.
The Floyd-Warshall Algorithm is a dynamic programming algorithm used to find shortest paths between all pairs of vertices in a weighted graph. This approach is more suited when there are frequent shortest path queries between multiple different node pairs.
This implementation uses Floyd-Warshall Algorithm, which precomputes shortest paths between all pairs of nodes. Post addEdge operations, the algorithm recomputes paths by potentially updating the distance matrix.
Time Complexity: O(n^3), where n is the number of vertices, arising from the three nested loops.
Space Complexity: O(n^2) due to the distance matrix storage covering all node pairs.
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.
In the addEdge function, we update the value of g_{ij} to edge[2].
In the shortestPath function, we use Dijsktra's algorithm to find the shortest path from node node1 to node node2. Here, dist[i] represents the shortest path from node node1 to node i, and vis[i] indicates whether node i has been visited. We initialize dist[node1] to 0, and the rest of dist[i] are all infty. Then we iterate n times, each time finding the current unvisited node t such that dist[t] is the smallest. Then we mark node t as visited, and then update the value of dist[i] to min(dist[i], dist[t] + g_{ti}). Finally, we return dist[node2]. If dist[node2] is infty, it means that there is no path from node node1 to node node2, so we return -1.
The time complexity is O(n^2 times q), and the space complexity is O(n^2). Where n is the number of nodes, and q is the number of calls to the shortestPath function.
| Approach | Complexity |
|---|---|
| Dijkstra's Algorithm | Time Complexity: O(V^2), where V is the number of vertices since we're using an adjacency matrix and no priority queue to obtain the minimum distance vertex. |
| Floyd-Warshall Algorithm | Time Complexity: O(n^3), where n is the number of vertices, arising from the three nested loops. |
| Dijsktra's Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra with Adjacency List | O((V + E) log V) per query | O(V + E) | General case with dynamic edge additions and moderate query count |
| Floyd–Warshall with Distance Matrix | O(V^3) preprocessing, O(1) query | O(V^2) | Small graphs with many shortest-path queries where constant-time lookup is valuable |
Design Graph With Shortest Path Calculator | Dijkstra’s | Floyd Warshall | Leetcode-2642 • codestorywithMIK • 5,468 views views
Watch 9 more video solutions →Practice Design Graph With Shortest Path Calculator with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor