Design Graph With Shortest Path Calculator · Interview Problem

Back to problems

Leetcode

Medium

Graphs

Design

Shortest Path

Heaps

Google

Amazon

Design Graph With Shortest Path Calculator

Design a graph data structure that supports adding directed weighted edges and answering shortest-path queries between nodes.

Acceptance 0%

Start Practice

Problem Statement

Design a Graph API

Implement a graph data structure that supports two operations:

Add an edge from one node to another with a non-negative weight.
Query the shortest distance between two nodes using the edges that have been added so far.

The graph is dynamic: edges may be added over time, and each shortest-path query should reflect all updates made before that query.

If no path exists between the requested nodes, return -1.

Your implementation should be efficient enough for repeated updates and queries.

Notes

Nodes are represented by integer labels.
Edges are directed.
Edge weights are non-negative.
You may assume the graph can contain multiple edges and cycles.

Input Format

A graph is initialized with a fixed number of nodes.
Then a sequence of operations is performed:
- addEdge(u, v, w) adds a directed edge from u to v with weight w.
- shortestPath(node1, node2) returns the minimum total weight from node1 to node2, or -1 if unreachable.

Output Format

For each shortest-path query, return the minimum distance as an integer.
If there is no valid path, return -1.

Constraints

1 <= n where n is the number of nodes.
Node labels are valid indices in the graph.
Edge weights are non-negative.
Queries and edge additions can be interleaved.
Multiple edges between the same nodes may exist.
Self-loops and cycles may appear.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 4
operations = [
  ["addEdge", 0, 1, 5],
  ["addEdge", 1, 2, 3],
  ["shortestPath", 0, 2],
  ["addEdge", 0, 2, 10],
  ["shortestPath", 0, 2],
  ["shortestPath", 2, 0]
]

Output

[8, 8, -1]

Explanation

The shortest path from 0 to 2 is 0 -> 1 -> 2 with total cost 8. Adding a direct edge 0 -> 2 with cost 10 does not improve it. There is no path from 2 back to 0.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress