# Design Graph With Shortest Path Calculator
**Difficulty:** HARD
[External](https://leetcode.com/problems/design-graph-with-shortest-path-calculator)
Canonical: https://scaleengineer.com/dsa/problems/design-graph-with-shortest-path-calculator
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [Nike](https://scaleengineer.com/companies/nike)
---
## Problem
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:**

![](https://assets.glich.co/dsa/design-graph-with-shortest-path-calculator/image0.png) 

**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`.

# Approaches
## On-Demand Calculation with Dijkstra's Algorithm
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.
**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.
**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.
### Explanation
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):**
1. Create an empty adjacency list for `n` nodes.
2. 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`):**
1. 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`):**
1. This is where the main work is done. We run Dijkstra's algorithm starting from `node1`.
2. 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]`.
3. 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.
4. Start by adding `[0, node1]` to the priority queue.
5. 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.
6. 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.
7. After the algorithm terminates, if the destination was reached, its distance is returned. Otherwise, no path exists, and we return -1.

```java
import java.util.*;

class Graph {
    private int n;
    private List<List<int[]>> adj;

    public Graph(int n, int[][] edges) {
        this.n = n;
        adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
    }
    
    public void addEdge(int[] edge) {
        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }
    
    public int shortestPath(int node1, int node2) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[node1] = 0;

        // PriorityQueue stores {distance, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, node1});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int d = current[0];
            int u = current[1];

            if (u == node2) {
                return d;
            }

            if (d > dist[u]) {
                continue;
            }

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        return -1;
    }
}
```
### 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.

## All-Pairs Shortest Path with Floyd-Warshall and Optimized Updates
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.
**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.
**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).
### Explanation
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):**
1. Initialize the `dist` matrix: `dist[i][i] = 0` and `dist[i][j] = infinity` for `i != j`. Using a `long` type for distances prevents overflow.
2. Populate the matrix with the initial edges: for each edge `(u, v, w)`, set `dist[u][v] = w`.
3. 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`):**
1. When a new edge `(u, v, w)` is added, we don't need to re-run the entire O(n^3) algorithm.
2. The new edge can potentially shorten the path between any pair of nodes `(i, j)`. A new potential path is `i -> ... -> u -> v -> ... -> j`.
3. The cost of this new path is `dist[i][u] + w + dist[v][j]`.
4. 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`):**
1. This is a simple O(1) lookup. Return `dist[node1][node2]`.
2. If `dist[node1][node2]` is infinity, no path exists, so return -1.

```java
import java.util.Arrays;

class Graph {
    private int n;
    private long[][] dist;
    private static final long INF = (long)1e12; // A large value for infinity

    public Graph(int n, int[][] edges) {
        this.n = n;
        dist = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int[] edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    public void addEdge(int[] edge) {
        int u = edge[0];
        int v = edge[1];
        long w = edge[2];

        // Check if this new edge can shorten any existing path
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][u] < INF && dist[v][j] < INF) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][u] + w + dist[v][j]);
                }
            }
        }
    }
    
    public int shortestPath(int node1, int node2) {
        if (dist[node1][node2] >= INF) {
            return -1;
        }
        return (int) dist[node1][node2];
    }
}
```
### 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.

# Solutions
### CSharp

```csharp
public 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); */
```

### Java

```java
class 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); */
```

### CPP

```cpp
class 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); */
```

### Python

```python
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)
```