2642. Design Graph With Shortest Path Calculator Solution

Q: Is Design Graph With Shortest Path Calculator easy or hard?

The problem is rated Hard because it combines graph algorithms with object-oriented design. You must implement a class that supports dynamic edge updates while computing shortest paths efficiently using algorithms like Dijkstra or Floyd–Warshall.

Q: Design Graph With Shortest Path Calculator Python/Java solution

Typical implementations use Dijkstra’s algorithm with a priority queue. Python solutions rely on the heapq module, while Java implementations commonly use PriorityQueue. The adjacency list stores neighbors and edge weights, enabling efficient traversal during each query.

Q: How to solve Design Graph With Shortest Path Calculator efficiently?

Maintain the graph with an adjacency list and run Dijkstra’s algorithm whenever a shortest path query is requested. Use a min-heap to always process the node with the smallest current distance. This ensures the optimal path is found efficiently even as edges are added dynamically.

Q: What is the best approach for Design Graph With Shortest Path Calculator?

Dijkstra’s algorithm with an adjacency list and priority queue is the most practical approach. Edge additions take O(1) time, and each shortest path query runs in O((V + E) log V). This balances dynamic updates and query performance well for most constraints.

Q: Is Design Graph With Shortest Path Calculator asked at Google/Amazon/Meta?

Graph design and shortest-path problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving Dijkstra’s algorithm, priority queues, and dynamic graph updates are common in system design and algorithm rounds.

Q: What data structure is used in Design Graph With Shortest Path Calculator?

The core structures are an adjacency list to represent the graph and a min-heap (priority queue) for Dijkstra’s algorithm. The heap ensures the next node with the smallest distance is processed first, which guarantees optimal shortest paths in weighted graphs with non-negative edges.

Q: What is the time complexity of Design Graph With Shortest Path Calculator?

Using Dijkstra’s algorithm, each shortest path query runs in O((V + E) log V) time due to the priority queue operations. Space complexity is O(V + E) for storing the adjacency list. Floyd–Warshall offers O(1) query time but requires O(V^3) preprocessing and O(V^2) space.

The 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] = [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.

Approach overview

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.

Approach 1: Dijkstra's Algorithm

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.

Python

import heapq

class Graph:
    def __init__(self, n, edges):
        self.n = n
        self.adj = [[] for _ in range(n)]
        for u, v, cost in edges:
            self.adj[u].append((v, cost))

    def addEdge(self, edge):
        u, v, cost = edge
        self.adj[u].append((v, cost))

    def shortestPath(self, node1, node2):
        dist = [float('inf')] * self.n
        dist[node1] = 0
        pq = [(0, node1)]

        while pq:
            curDist, u = heapq.heappop(pq)
            if u == node2:
                return curDist
            if curDist > dist[u]:
                continue
            for v, cost in self.adj[u]:
                if dist[u] + cost < dist[v]:
                    dist[v] = dist[u] + cost
                    heapq.heappush(pq, (dist[v], v))
        return -1

# Demonstration
if __name__ == "__main__":
    edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
    graph = Graph(4, edges)
    print(graph.shortestPath(3, 2))  # Output: 6
    print(graph.shortestPath(0, 3))  # Output: -1
    graph.addEdge([1, 3, 4])
    print(graph.shortestPath(0, 3))  # Output: 6

Java

import java.util.*;

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

    public Graph(int n, int[][] edges) {
        this.n = n;
        this.adj = new ArrayList<>();
        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<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{node1, 0});

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

            if (u == node2) return curDist;
            if (curDist > dist[u]) continue;

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

    public static void main(String[] args) {
        int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
        Graph graph = new Graph(4, edges);
        System.out.println(graph.shortestPath(3, 2)); // Output: 6
        System.out.println(graph.shortestPath(0, 3)); // Output: -1
        graph.addEdge(new int[]{1, 3, 4});
        System.out.println(graph.shortestPath(0, 3)); // Output: 6
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

class Graph {
public:
    int n;
    vector<vector<pair<int, int>>> adj;

    Graph(int n, vector<vector<int>>& edges) : n(n) {
        adj.resize(n);
        for (const auto& edge : edges) {
            adj[edge[0]].emplace_back(edge[1], edge[2]);
        }
    }

    void addEdge(vector<int> edge) {
        adj[edge[0]].emplace_back(edge[1], edge[2]);
    }

    int shortestPath(int node1, int node2) {
        vector<int> dist(n, numeric_limits<int>::max());
        dist[node1] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.emplace(0, node1);

        while (!pq.empty()) {
            auto [curDist, u] = pq.top(); pq.pop();

            if (u == node2) return curDist;
            if (curDist > dist[u]) continue;

            for (auto [v, cost] : adj[u]) {
                if (dist[u] + cost < dist[v]) {
                    dist[v] = dist[u] + cost;
                    pq.emplace(dist[v], v);
                }
            }
        }
        return -1;
    }
};

int main() {
    vector<vector<int>> edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
    Graph* g = new Graph(4, edges);
    cout << g->shortestPath(3, 2) << endl; // Output: 6
    cout << g->shortestPath(0, 3) << endl; // Output: -1
    g->addEdge({1, 3, 4});
    cout << g->shortestPath(0, 3) << endl; // Output: 6
    delete g;
    return 0;
}

JavaScript

class Graph {
    constructor(n, edges) {
        this.n = n;
        this.adj = Array.from({ length: n }, () => []);
        for (const [u, v, cost] of edges) {
            this.adj[u].push([v, cost]);
        }
    }

    addEdge(edge) {
        const [u, v, cost] = edge;
        this.adj[u].push([v, cost]);
    }

    shortestPath(node1, node2) {
        const dist = new Array(this.n).fill(Infinity);
        dist[node1] = 0;
        const pq = new PriorityQueue((a, b) => a[0] < b[0]);
        pq.enqueue([0, node1]);

        while (!pq.isEmpty()) {
            const [curDist, u] = pq.dequeue();
            if (u === node2) return curDist;
            if (curDist > dist[u]) continue;

            for (const [v, cost] of this.adj[u]) {
                if (dist[u] + cost < dist[v]) {
                    dist[v] = dist[u] + cost;
                    pq.enqueue([dist[v], v]);
                }
            }
        }
        return -1;
    }
}

class PriorityQueue {
    constructor(comparator) {
        this.data = [];
        this.comparator = comparator;
    }

    enqueue(value) {
        this.data.push(value);
        this.data.sort(this.comparator);
    }

    dequeue() {
        return this.data.shift();
    }

    isEmpty() {
        return this.data.length === 0;
    }
}

// Demonstration
const edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]];
const graph = new Graph(4, edges);
console.log(graph.shortestPath(3, 2)); // Output: 6
console.log(graph.shortestPath(0, 3)); // Output: -1
graph.addEdge([1, 3, 4]);
console.log(graph.shortestPath(0, 3)); // Output: 6

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define INF INT_MAX

typedef struct {
    int u, v, cost;
} Edge;

typedef struct {
    int n;
    Edge* edges;
    int edgesSize;
} Graph;

Graph* createGraph(int n, int edgesSize, int edges[edgesSize][3]) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->n = n;
    graph->edgesSize = edgesSize;
    graph->edges = (Edge*)malloc(sizeof(Edge) * edgesSize);
    for (int i = 0; i < edgesSize; i++) {
        graph->edges[i].u = edges[i][0];
        graph->edges[i].v = edges[i][1];
        graph->edges[i].cost = edges[i][2];
    }
    return graph;
}

void addEdge(Graph* graph, int from, int to, int cost) {
    graph->edges = (Edge*)realloc(graph->edges, sizeof(Edge) * (graph->edgesSize + 1));
    graph->edges[graph->edgesSize].u = from;
    graph->edges[graph->edgesSize].v = to;
    graph->edges[graph->edgesSize].cost = cost;
    graph->edgesSize++;
}

int minDistance(int dist[], int sptSet[], int n) {
    int min = INF, min_index;
    for (int v = 0; v < n; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

int dijkstra(Graph* graph, int src, int dest) {
    int n = graph->n;
    int dist[n];
    int sptSet[n];

    for (int i = 0; i < n; i++)
        dist[i] = INF, sptSet[i] = 0;

    dist[src] = 0;

    for (int count = 0; count < n - 1; count++) {
        int u = minDistance(dist, sptSet, n);
        sptSet[u] = 1;

        for (int v = 0; v < n; v++)
            if (!sptSet[v] && dist[u] != INF && dist[u] + graph->adjMatrix[u][v] < dist[v])
                dist[v] = dist[u] + graph->adjMatrix[u][v];
    }

    return dist[dest] == INF ? -1 : dist[dest];
}

int shortestPath(Graph* graph, int node1, int node2) {
    return dijkstra(graph, node1, node2);
}

int main() {
    int edges[4][3] = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
    Graph* graph = createGraph(4, 4, edges);
    printf("%d\n", shortestPath(graph, 3, 2)); // Output: 6
    printf("%d\n", shortestPath(graph, 0, 3)); // Output: -1
    addEdge(graph, 1, 3, 4);
    printf("%d\n", shortestPath(graph, 0, 3)); // Output: 6
    free(graph->edges);
    free(graph);
    return 0;
}

using System;
using System.Collections.Generic;

public class Graph {
    private int n;
    private List<List<(int, int)>> adj;

    public Graph(int n, int[][] edges) {
        this.n = n;
        this.adj = new List<List<(int, int)>>();
        for (int i = 0; i < n; i++) {
            adj.Add(new List<(int, int)>());
        }
        foreach (var edge in edges) {
            adj[edge[0]].Add((edge[1], edge[2]));
        }
    }

    public void AddEdge(int[] edge) {
        adj[edge[0]].Add((edge[1], edge[2]));
    }

    public int ShortestPath(int node1, int node2) {
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[node1] = 0;

        var pq = new SortedSet<(int Distance, int Vertex)>(Comparer<(int, int)>.Create((x, y) => {
            int result = x.Distance.CompareTo(y.Distance);
            return result == 0 ? x.Vertex.CompareTo(y.Vertex) : result;
        }));
        pq.Add((0, node1));

        while (pq.Count > 0) {
            var current = pq.Min;
            pq.Remove(current);
            int u = current.Vertex;
            int curDist = current.Distance;

            if (u == node2) return curDist;
            if (curDist > dist[u]) continue;

            foreach (var (v, cost) in adj[u]) {
                if (dist[u] + cost < dist[v]) {
                    dist[v] = dist[u] + cost;
                    pq.Add((dist[v], v));
                }
            }
        }
        return -1;
    }

    public static void Main() {
        int[][] edges = new int[][] { new int[] { 0, 2, 5 }, new int[] { 0, 1, 2 }, new int[] { 1, 2, 1 }, new int[] { 3, 0, 3 } };
        Graph g = new Graph(4, edges);
        Console.WriteLine(g.ShortestPath(3, 2)); // Output: 6
        Console.WriteLine(g.ShortestPath(0, 3)); // Output: -1
        g.AddEdge(new int[] { 1, 3, 4 });
        Console.WriteLine(g.ShortestPath(0, 3)); // Output: 6
    }
}

Python implementation utilizes `heapq` for the priority queue, allowing Dijkstra's approach to effectively evaluate the shortest path by updating minimum costs as graph exploration progresses.

Complexity

Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices, justified by priority queue operations.
Space Complexity: O(V + E) due to storage for adjacency list and distance estimates.

Try this approach in the editor

Approach 2: Floyd-Warshall Algorithm

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.

Python

class Graph:
    def __init__(self, n, edges):
        self.n = n
        self.dist = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            self.dist[i][i] = 0
        for u, v, cost in edges:
            self.dist[u][v] = cost
        self.floyd_warshall()

    def floyd_warshall(self):
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if self.dist[i][k] != float('inf') and self.dist[k][j] != float('inf'):
                        self.dist[i][j] = min(self.dist[i][j], self.dist[i][k] + self.dist[k][j])

    def addEdge(self, edge):
        u, v, cost = edge
        self.dist[u][v] = cost
        self.floyd_warshall()

    def shortestPath(self, node1, node2):
        return -1 if self.dist[node1][node2] == float('inf') else self.dist[node1][node2]

# Demonstration
if __name__ == "__main__":
    edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
    graph = Graph(4, edges)
    print(graph.shortestPath(3, 2))  # Output: 6
    print(graph.shortestPath(0, 3))  # Output: -1
    graph.addEdge([1, 3, 4])
    print(graph.shortestPath(0, 3))  # Output: 6

Java

import java.util.*;

class Graph {
    private int n;
    private int[][] dist;

    public Graph(int n, int[][] edges) {
        this.n = n;
        dist = new int[n][n];
        for (int[] row : dist)
            Arrays.fill(row, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++)
            dist[i][i] = 0;
        for (int[] edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
        }
        floydWarshall();
    }

    public void floydWarshall() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE)
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    public void addEdge(int[] edge) {
        dist[edge[0]][edge[1]] = edge[2];
        floydWarshall();
    }

    public int shortestPath(int node1, int node2) {
        return dist[node1][node2] == Integer.MAX_VALUE ? -1 : dist[node1][node2];
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
        Graph graph = new Graph(4, edges);
        System.out.println(graph.shortestPath(3, 2)); // Output: 6
        System.out.println(graph.shortestPath(0, 3)); // Output: -1
        graph.addEdge(new int[]{1, 3, 4});
        System.out.println(graph.shortestPath(0, 3)); // Output: 6
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

class Graph {
public:
    int n;
    vector<vector<int>> dist;

    Graph(int n, vector<vector<int>>& edges) : n(n) {
        dist.assign(n, vector<int>(n, numeric_limits<int>::max()));
        for (int i = 0; i < n; i++) dist[i][i] = 0;
        for (const auto& edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
        }
        floydWarshall();
    }

    void floydWarshall() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != numeric_limits<int>::max() && dist[k][j] != numeric_limits<int>::max())
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    void addEdge(vector<int> edge) {
        dist[edge[0]][edge[1]] = edge[2];
        floydWarshall();
    }

    int shortestPath(int node1, int node2) {
        return dist[node1][node2] == numeric_limits<int>::max() ? -1 : dist[node1][node2];
    }
};

int main() {
    vector<vector<int>> edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
    Graph g(4, edges);
    cout << g.shortestPath(3, 2) << endl; // Output: 6
    cout << g.shortestPath(0, 3) << endl; // Output: -1
    g.addEdge({1, 3, 4});
    cout << g.shortestPath(0, 3) << endl; // Output: 6
    return 0;
}

JavaScript

class Graph {
    constructor(n, edges) {
        this.n = n;
        this.dist = Array.from({ length: n }, () => Array(n).fill(Infinity));
        for (let i = 0; i < n; i++) {
            this.dist[i][i] = 0;
        }
        for (const [u, v, cost] of edges) {
            this.dist[u][v] = cost;
        }
        this.floydWarshall();
    }

    floydWarshall() {
        const { n, dist } = this;
        for (let k = 0; k < n; k++) {
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    if (dist[i][k] < Infinity && dist[k][j] < Infinity) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }

    addEdge(edge) {
        const [u, v, cost] = edge;
        this.dist[u][v] = cost;
        this.floydWarshall();
    }

    shortestPath(node1, node2) {
        return this.dist[node1][node2] === Infinity ? -1 : this.dist[node1][node2];
    }
}

// Demonstration
const edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]];
const graph = new Graph(4, edges);
console.log(graph.shortestPath(3, 2)); // Output: 6
console.log(graph.shortestPath(0, 3)); // Output: -1
graph.addEdge([1, 3, 4]);
console.log(graph.shortestPath(0, 3)); // Output: 6

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define INF INT_MAX

typedef struct {
    int n;
    int** dist;
} Graph;

Graph* createGraph(int n, int edges[][3], int edgesSize) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->n = n;
    graph->dist = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        graph->dist[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++)
            graph->dist[i][j] = (i == j) ? 0 : INF;
    }
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        graph->dist[u][v] = edges[i][2];
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph->dist[i][k] != INF && graph->dist[k][j] != INF)
                    graph->dist[i][j] = (graph->dist[i][j] > graph->dist[i][k] + graph->dist[k][j]) ? graph->dist[i][k] + graph->dist[k][j] : graph->dist[i][j];
            }
        }
    }
    
    return graph;
}

void addEdge(Graph* graph, int u, int v, int cost) {
    graph->dist[u][v] = cost;
    // Re-run Floyd-Warshall
    for (int k = 0; k < graph->n; k++) {
        for (int i = 0; i < graph->n; i++) {
            for (int j = 0; j < graph->n; j++) {
                if (graph->dist[i][k] != INF && graph->dist[k][j] != INF)
                    graph->dist[i][j] = (graph->dist[i][j] > graph->dist[i][k] + graph->dist[k][j]) ? graph->dist[i][k] + graph->dist[k][j] : graph->dist[i][j];
            }
        }
    }
}

int shortestPath(Graph* graph, int node1, int node2) {
    if(graph->dist[node1][node2] == INF)
        return -1;
    return graph->dist[node1][node2];
}

int main() {
    int edges[4][3] = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
    Graph* graph = createGraph(4, edges, 4);
    printf("%d\n", shortestPath(graph, 3, 2)); // Output: 6
    printf("%d\n", shortestPath(graph, 0, 3)); // Output: -1
    addEdge(graph, 1, 3, 4);
    printf("%d\n", shortestPath(graph, 0, 3)); // Output: 6
    
    // Free the memory
    for(int i = 0; i < graph->n; i++)
        free(graph->dist[i]);
    free(graph->dist);
    free(graph);
    return 0;
}

using System;

public class Graph {
    private int n;
    private int[,] dist;

    public Graph(int n, int[][] edges) {
        this.n = n;
        dist = new int[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i, j] = (i == j) ? 0 : int.MaxValue;
        foreach (var edge in edges)
            dist[edge[0], edge[1]] = edge[2];
        FloydWarshall();
    }

    private void FloydWarshall() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue)
                        dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
                }
            }
        }
    }

    public void AddEdge(int[] edge) {
        dist[edge[0], edge[1]] = edge[2];
        FloydWarshall();
    }

    public int ShortestPath(int node1, int node2) {
        return dist[node1, node2] == int.MaxValue ? -1 : dist[node1, node2];
    }

    public static void Main(String[] args) {
        int[][] edges = new int[][] { new int[] { 0, 2, 5 }, new int[] { 0, 1, 2 }, new int[] { 1, 2, 1 }, new int[] { 3, 0, 3 } };
        Graph graph = new Graph(4, edges);
        Console.WriteLine(graph.ShortestPath(3, 2)); // Output: 6
        Console.WriteLine(graph.ShortestPath(0, 3)); // Output: -1
        graph.AddEdge(new int[] { 1, 3, 4 });
        Console.WriteLine(graph.ShortestPath(0, 3)); // Output: 6
    }
}

Python computes all pairs’ shortest paths upfront, storing these for efficient query handling, factoring additional edges via necessary resultant matrix updates.

Complexity

Time Complexity: O(n^3) intrinsic to triple-layer loop searches.
Space Complexity: O(n^2) occupied by all-pairs distance records.

Try this approach in the editor

Approach 3: 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.

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.

TypeScript

class Graph {
    private g: number[][] = [];
    private inf: number = 1 << 29;

    constructor(n: number, edges: number[][]) {
        this.g = Array.from({ length: n }, () => Array(n).fill(this.inf));
        for (const [f, t, c] of edges) {
            this.g[f][t] = c;
        }
    }

    addEdge(edge: number[]): void {
        const [f, t, c] = edge;
        this.g[f][t] = c;
    }

    shortestPath(node1: number, node2: number): number {
        const n = this.g.length;
        const dist: number[] = new Array(n).fill(this.inf);
        dist[node1] = 0;
        const vis: boolean[] = new Array(n).fill(false);
        for (let i = 0; i < n; ++i) {
            let t = -1;
            for (let j = 0; j < n; ++j) {
                if (!vis[j] && (t === -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            vis[t] = true;
            for (let j = 0; j < n; ++j) {
                dist[j] = Math.min(dist[j], dist[t] + this.g[t][j]);
            }
        }
        return dist[node2] >= this.inf ? -1 : dist[node2];
    }
}

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

const inf = 1 << 29

type Graph struct {
	g [][]int
}

func Constructor(n int, edges [][]int) Graph {
	g := make([][]int, n)
	for i := range g {
		g[i] = make([]int, n)
		for j := range g[i] {
			g[i][j] = inf
		}
	}
	for _, e := range edges {
		f, t, c := e[0], e[1], e[2]
		g[f][t] = c
	}
	return Graph{g}
}

func (this *Graph) AddEdge(edge []int) {
	f, t, c := edge[0], edge[1], edge[2]
	this.g[f][t] = c
}

func (this *Graph) ShortestPath(node1 int, node2 int) int {
	n := len(this.g)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = inf
	}
	vis := make([]bool, n)
	dist[node1] = 0
	for i := 0; i < n; i++ {
		t := -1
		for j := 0; j < n; j++ {
			if !vis[j] && (t == -1 || dist[t] > dist[j]) {
				t = j
			}
		}
		vis[t] = true
		for j := 0; j < n; j++ {
			dist[j] = min(dist[j], dist[t]+this.g[t][j])
		}
	}
	if dist[node2] >= inf {
		return -1
	}
	return dist[node2]
}

/**
 * Your Graph object will be instantiated and called as such:
 * obj := Constructor(n, edges);
 * obj.AddEdge(edge);
 * param_2 := obj.ShortestPath(node1,node2);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dijkstra's Algorithm	Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices, justified by priority queue operations. Space Complexity: O(V + E) due to storage for adjacency list and distance estimates.
Floyd-Warshall Algorithm	Time Complexity: O(n^3) intrinsic to triple-layer loop searches. Space Complexity: O(n^2) occupied by all-pairs distance records.
Dijsktra's Algorithm	–

Complexity analysis

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

Frequently asked questions

Is Design Graph With Shortest Path Calculator easy or hard?

The problem is rated Hard because it combines graph algorithms with object-oriented design. You must implement a class that supports dynamic edge updates while computing shortest paths efficiently using algorithms like Dijkstra or Floyd–Warshall.

Design Graph With Shortest Path Calculator Python/Java solution

Typical implementations use Dijkstra’s algorithm with a priority queue. Python solutions rely on the heapq module, while Java implementations commonly use PriorityQueue. The adjacency list stores neighbors and edge weights, enabling efficient traversal during each query.

How to solve Design Graph With Shortest Path Calculator efficiently?

Maintain the graph with an adjacency list and run Dijkstra’s algorithm whenever a shortest path query is requested. Use a min-heap to always process the node with the smallest current distance. This ensures the optimal path is found efficiently even as edges are added dynamically.

What is the best approach for Design Graph With Shortest Path Calculator?

Dijkstra’s algorithm with an adjacency list and priority queue is the most practical approach. Edge additions take O(1) time, and each shortest path query runs in O((V + E) log V). This balances dynamic updates and query performance well for most constraints.

Is Design Graph With Shortest Path Calculator asked at Google/Amazon/Meta?

Graph design and shortest-path problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving Dijkstra’s algorithm, priority queues, and dynamic graph updates are common in system design and algorithm rounds.

What data structure is used in Design Graph With Shortest Path Calculator?

The core structures are an adjacency list to represent the graph and a min-heap (priority queue) for Dijkstra’s algorithm. The heap ensures the next node with the smallest distance is processed first, which guarantees optimal shortest paths in weighted graphs with non-negative edges.

What is the time complexity of Design Graph With Shortest Path Calculator?

Using Dijkstra’s algorithm, each shortest path query runs in O((V + E) log V) time due to the priority queue operations. Space complexity is O(V + E) for storing the adjacency list. Floyd–Warshall offers O(1) query time but requires O(V^3) preprocessing and O(V^2) space.

Design Graph With Shortest Path Calculator solution and explanation

The problem

Approach overview

Approach 1: Dijkstra's Algorithm

Approach 2: Floyd-Warshall Algorithm

Approach 3: Dijsktra's Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Graph With Shortest Path Calculator solution and explanation

The problem

Approach overview

Approach 1: Dijkstra's Algorithm

Approach 2: Floyd-Warshall Algorithm

Approach 3: Dijsktra's Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems