Skip to main content
Talentd

Design Graph With Shortest Path Calculator - Solution & Explanation

HardGraphDesignHeap (Priority Queue)Shortest Path27 min readAsked at: Samsung, Nike
Practice this problem

Problem Statement

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

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(V^2) due to the adjacency matrix storage requirements.

Floyd-Warshall Algorithm

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.

Dijsktra's Algorithm—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dijkstra with Adjacency ListO((V + E) log V) per queryO(V + E)General case with dynamic edge additions and moderate query count
Floyd–Warshall with Distance MatrixO(V^3) preprocessing, O(1) queryO(V^2)Small graphs with many shortest-path queries where constant-time lookup is valuable

Video Solution

Design Graph With Shortest Path Calculator | Dijkstra’s | Floyd Warshall | Leetcode-2642 • codestorywithMIK • 5,961 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Design Graph With Shortest Path Calculator with our built-in code editor and test cases.

Practice on FleetCode
Previous

Closest Node to Path in Tree

Next

Number of Restricted Paths From First to Last Node