Design Graph With Shortest Path Calculator

Hard

#2402Time: - `Graph()`: O(E), where E is the initial number of edges. - `addEdge()`: O(1). - `shortestPath()`: O(E' log n), where E' is the current number of edges. In the worst case, E' is O(n^2), making the complexity O(n^2 log n).Space: O(n + E'), where `n` is the number of nodes and `E'` is the current number of edges. This space is used for the adjacency list.2 companies

Patterns

Design

Algorithms

Shortest Path

Data structures

Heap (Priority Queue)Graph

Companies

Samsung Nike

Prompt

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] = [from_i, to_i, edgeCost_i] meaning that there is an edge from from_i to to_i with the cost edgeCost_i.

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 <= 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⁶
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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach calculates the shortest path only when the shortestPath method is called. It uses an adjacency list to represent the graph, which is efficient for storing graph structures. Adding a new edge is a very fast operation. The main computation happens inside the shortestPath method, where Dijkstra's algorithm is run from the source node to find the shortest path to the destination node.

Algorithm

Graph(n, edges):
1. Create an adjacency list adj of size n.
2. For each edge (u, v, w) in the input edges, add a pair (v, w) to the list adj[u].
addEdge(edge):
1. Given a new edge (u, v, w), add the pair (v, w) to the list adj[u].
shortestPath(node1, node2):
1. Initialize a distances array of size n with infinity, and set distances[node1] = 0.
2. Create a priority queue pq to store pairs of (cost, node), ordered by cost.
3. Add (0, node1) to pq.
4. While pq is not empty: a. Extract the node u with the smallest cost d from pq. b. If u is the destination node2, return d. c. If d is greater than the already known distance to u, skip. d. For each neighbor v of u with edge weight w: i. If a shorter path is found (distances[u] + w < distances[v]): - Update distances[v] = distances[u] + w. - Add (distances[v], v) to pq.
5. If the loop completes and node2 was not reached, return -1.

Walkthrough

The graph is stored using an adjacency list, where for each node, we store a list of its outgoing edges and their costs. A List<List<int[]>> is a suitable data structure, where adj.get(u) contains pairs of [v, cost] for all edges from u to v.

Initialization (Graph constructor):

Create an empty adjacency list for n nodes.
Iterate through the initial edges array and populate the adjacency list. For each edge [from, to, cost], add [to, cost] to the list for from.

Adding an Edge (addEdge):

This is a simple and fast operation. Given an edge [from, to, cost], just add [to, cost] to the adjacency list of the from node.

Finding Shortest Path (shortestPath):

This is where the main work is done. We run Dijkstra's algorithm starting from node1.
We need a priority queue to efficiently retrieve the node with the smallest distance to visit next. The priority queue will store pairs of [cost, node].
We also need a distances array to keep track of the minimum cost found so far from node1 to every other node. Initialize all distances to infinity, except for distances[node1], which is 0.
Start by adding [0, node1] to the priority queue.
While the priority queue is not empty, extract the node u with the minimum cost. If this node is the destination, we have found the shortest path.
For each neighbor v of u, if a shorter path to v is found (i.e., distances[u] + cost(u,v) < distances[v]), update distances[v] and add [distances[v], v] to the priority queue.
After the algorithm terminates, if the destination was reached, its distance is returned. Otherwise, no path exists, and we return -1.

1import java.util.*;2 3class Graph {4    private int n;5    private List<List<int[]>> adj;6 7    public Graph(int n, int[][] edges) {8        this.n = n;9        adj = new ArrayList<>(n);10        for (int i = 0; i < n; i++) {11            adj.add(new ArrayList<>());12        }13        for (int[] edge : edges) {14            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});15        }16    }17    18    public void addEdge(int[] edge) {19        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});20    }21    22    public int shortestPath(int node1, int node2) {23        int[] dist = new int[n];24        Arrays.fill(dist, Integer.MAX_VALUE);25        dist[node1] = 0;26 27        // PriorityQueue stores {distance, node}28        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));29        pq.offer(new int[]{0, node1});30 31        while (!pq.isEmpty()) {32            int[] current = pq.poll();33            int d = current[0];34            int u = current[1];35 36            if (u == node2) {37                return d;38            }39 40            if (d > dist[u]) {41                continue;42            }43 44            for (int[] edge : adj.get(u)) {45                int v = edge[0];46                int weight = edge[1];47                if (dist[u] + weight < dist[v]) {48                    dist[v] = dist[u] + weight;49                    pq.offer(new int[]{dist[v], v});50                }51            }52        }53 54        return -1;55    }56}

Complexity

Time

- `Graph()`: O(E), where E is the initial number of edges. - `addEdge()`: O(1). - `shortestPath()`: O(E' log n), where E' is the current number of edges. In the worst case, E' is O(n^2), making the complexity O(n^2 log n).

Space

O(n + E'), where `n` is the number of nodes and `E'` is the current number of edges. This space is used for the adjacency list.

Trade-offs

Pros

addEdge is very fast, taking constant time O(1).
Space-efficient for sparse graphs, as it only stores existing edges.
Conceptually straightforward if Dijkstra's algorithm is familiar.

Cons

shortestPath can be slow if called frequently, as it re-computes paths from scratch every time.
For dense graphs, the performance degrades to O(n^2 log n) per query, which can be slower than other approaches for the given constraints.

This approach pre-computes the shortest paths between all pairs of nodes using the Floyd-Warshall algorithm and stores them in a 2D matrix. This makes shortestPath queries instantaneous (O(1)). When a new edge is added, instead of a full O(n^3) re-computation, an optimized O(n^2) update step is performed. For the given problem constraints, this trade-off makes it more efficient overall than re-running Dijkstra's algorithm for each query.

Algorithm

Graph(n, edges):
1. Create an n x n matrix dist, initialized with a large value for infinity, and dist[i][i] = 0.
2. For each initial edge (u, v, w), set dist[u][v] = w.
3. Run the Floyd-Warshall algorithm: for k from 0 to n-1, then for i from 0 to n-1, and for j from 0 to n-1, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
addEdge(edge):
1. Let the new edge be (u, v, w).
2. For each pair of nodes (i, j), check if the path through the new edge is shorter: dist[i][j] = min(dist[i][j], dist[i][u] + w + dist[v][j]).
shortestPath(node1, node2):
1. Look up dist[node1][node2].
2. If the value is infinity, return -1. Otherwise, return the value.

Walkthrough

We maintain an n x n matrix, dist, where dist[i][j] stores the cost of the shortest path from node i to node j.

Initialization (Graph constructor):

Initialize the dist matrix: dist[i][i] = 0 and dist[i][j] = infinity for i != j. Using a long type for distances prevents overflow.
Populate the matrix with the initial edges: for each edge (u, v, w), set dist[u][v] = w.
Run the full Floyd-Warshall algorithm with three nested loops (k, i, j) to compute all-pairs shortest paths. The update rule is dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Adding an Edge (addEdge):

When a new edge (u, v, w) is added, we don't need to re-run the entire O(n^3) algorithm.
The new edge can potentially shorten the path between any pair of nodes (i, j). A new potential path is i -> ... -> u -> v -> ... -> j.
The cost of this new path is dist[i][u] + w + dist[v][j].
We iterate through all pairs (i, j) and update dist[i][j] if this new path is shorter. This update step takes O(n^2) time.

Finding Shortest Path (shortestPath):

This is a simple O(1) lookup. Return dist[node1][node2].
If dist[node1][node2] is infinity, no path exists, so return -1.

1import java.util.Arrays;2 3class Graph {4    private int n;5    private long[][] dist;6    private static final long INF = (long)1e12; // A large value for infinity7 8    public Graph(int n, int[][] edges) {9        this.n = n;10        dist = new long[n][n];11        for (int i = 0; i < n; i++) {12            Arrays.fill(dist[i], INF);13            dist[i][i] = 0;14        }15 16        for (int[] edge : edges) {17            dist[edge[0]][edge[1]] = edge[2];18        }19 20        for (int k = 0; k < n; k++) {21            for (int i = 0; i < n; i++) {22                for (int j = 0; j < n; j++) {23                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);24                }25            }26        }27    }28    29    public void addEdge(int[] edge) {30        int u = edge[0];31        int v = edge[1];32        long w = edge[2];33 34        // Check if this new edge can shorten any existing path35        for (int i = 0; i < n; i++) {36            for (int j = 0; j < n; j++) {37                if (dist[i][u] < INF && dist[v][j] < INF) {38                    dist[i][j] = Math.min(dist[i][j], dist[i][u] + w + dist[v][j]);39                }40            }41        }42    }43    44    public int shortestPath(int node1, int node2) {45        if (dist[node1][node2] >= INF) {46            return -1;47        }48        return (int) dist[node1][node2];49    }50}

Complexity

Time

- `Graph()`: O(n^3) for the initial Floyd-Warshall computation. - `addEdge()`: O(n^2) for the optimized update. - `shortestPath()`: O(1).

Space

O(n^2) to store the all-pairs shortest path matrix.

Trade-offs

Pros

shortestPath queries are extremely fast, taking O(1) time.
addEdge is faster (O(n^2)) than a full re-computation (O(n^3)).
For the given constraints (n <= 100, frequent addEdge and shortestPath calls), this approach is more performant overall.

Cons

High initial setup cost of O(n^3) in the constructor.
High space complexity of O(n^2), which can be an issue for very large n (though acceptable for n <= 100).

Solutions

Solution

1public class Graph { private int n ; private int [][] g ; private readonly int inf = 1 << 29 ; public Graph ( int n , int [][] edges ) { this . n = n ; g = new int [ n ][]; for ( int i = 0 ; i < n ; i ++) { g [ i ] = new int [ n ]; for ( int j = 0 ; j < n ; j ++) { g [ i ][ j ] = inf ; } } foreach ( int [] e in edges ) { g [ e [ 0 ]][ e [ 1 ]] = e [ 2 ]; } } public void AddEdge ( int [] edge ) { g [ edge [ 0 ]][ edge [ 1 ]] = edge [ 2 ]; } public int ShortestPath ( int node1 , int node2 ) { int [] dist = new int [ n ]; bool [] vis = new bool [ n ]; Array . Fill ( dist , inf ); dist [ node1 ] = 0 ; for ( int i = 0 ; i < n ; i ++) { int t = - 1 ; for ( int j = 0 ; j < n ; j ++) { if (! vis [ j ] && ( t == - 1 || dist [ t ] > dist [ j ])) t = j ; } vis [ t ] = true ; for ( int j = 0 ; j < n ; j ++) { dist [ j ] = Math . Min ( dist [ j ], dist [ t ] + g [ t ][ j ]); } } return dist [ node2 ] >= inf ? - 1 : dist [ node2 ]; } } /** * Your Graph object will be instantiated and called as such: * Graph obj = new Graph(n, edges); * obj.AddEdge(edge); * int param_2 = obj.ShortestPath(node1,node2); */

1class Graph { private int n ; private int [][] g ; private final int inf = 1 << 29 ; public Graph ( int n , int [][] edges ) { this . n = n ; g = new int [ n ][ n ]; for ( var f : g ) { Arrays . fill ( f , inf ); } for ( int [] e : edges ) { int f = e [ 0 ], t = e [ 1 ], c = e [ 2 ]; g [ f ][ t ] = c ; } } public void addEdge ( int [] edge ) { int f = edge [ 0 ], t = edge [ 1 ], c = edge [ 2 ]; g [ f ][ t ] = c ; } public int shortestPath ( int node1 , int node2 ) { int [] dist = new int [ n ]; boolean [] vis = new boolean [ n ]; Arrays . fill ( dist , inf ); dist [ node1 ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int t = - 1 ; for ( int j = 0 ; j < n ; ++ j ) { if (! vis [ j ] && ( t == - 1 || dist [ t ] > dist [ j ])) { t = j ; } } vis [ t ] = true ; for ( int j = 0 ; j < n ; ++ j ) { dist [ j ] = Math . min ( dist [ j ], dist [ t ] + g [ t ][ j ]); } } return dist [ node2 ] >= inf ? - 1 : dist [ node2 ]; } } /** * Your Graph object will be instantiated and called as such: * Graph obj = new Graph(n, edges); * obj.addEdge(edge); * int param_2 = obj.shortestPath(node1,node2); */

1class Graph { public: Graph ( int n , vector < vector < int >>& edges ) { this -> n = n ; g = vector < vector < int >> ( n , vector < int > ( n , inf )); for ( auto & e : edges ) { int f = e [ 0 ], t = e [ 1 ], c = e [ 2 ]; g [ f ][ t ] = c ; } } void addEdge ( vector < int > edge ) { int f = edge [ 0 ], t = edge [ 1 ], c = edge [ 2 ]; g [ f ][ t ] = c ; } int shortestPath ( int node1 , int node2 ) { vector < bool > vis ( n ); vector < int > dist ( n , inf ); dist [ node1 ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int t = - 1 ; for ( int j = 0 ; j < n ; ++ j ) { if ( ! vis [ j ] && ( t == - 1 || dist [ t ] > dist [ j ])) { t = j ; } } vis [ t ] = true ; for ( int j = 0 ; j < n ; ++ j ) { dist [ j ] = min ( dist [ j ], dist [ t ] + g [ t ][ j ]); } } return dist [ node2 ] >= inf ? - 1 : dist [ node2 ]; } private: vector < vector < int >> g ; int n ; const int inf = 1 << 29 ; }; /** * Your Graph object will be instantiated and called as such: * Graph* obj = new Graph(n, edges); * obj->addEdge(edge); * int param_2 = obj->shortestPath(node1,node2); */

1class 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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem