LeetCode 2642 - Design Graph With Shortest Path Calculator

Difficulty: 🔴 Hard
Topics: Graph Theory, Design, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

The problem asks us to design a graph data structure that supports two operations efficiently:

Dynamically adding directed weighted edges.
Finding the shortest path cost between two nodes.

We are given a directed weighted graph with n nodes labeled from 0 to n - 1. The graph initially contains a list of edges, where each edge is represented as:

[from, to, edgeCost]

This means there is a directed edge from from to to with a travel cost of edgeCost.

We need to implement a Graph class with the following methods:

Graph(n, edges) initializes the graph.
addEdge(edge) inserts a new directed edge.
shortestPath(node1, node2) computes the minimum total cost to travel from node1 to node2.

If there is no valid path between the two nodes, we must return -1.

An important detail is that the graph is directed, meaning an edge from u -> v does not imply an edge from v -> u.

For example:

0 -> 1 (cost 2)
1 -> 2 (cost 1)

allows travel from 0 to 2 with cost 3, but not necessarily from 2 to 0.

The graph is also weighted, meaning edges have different traversal costs. Because of this, a shortest path is not necessarily the one with the fewest edges. Instead, we must minimize the sum of edge weights.

The constraints provide important hints about the problem scale:

n <= 100, which is very small.
At most 100 calls to addEdge.
At most 100 calls to shortestPath.

Since the graph size is small, we have flexibility in algorithm choice. We do not necessarily need the most theoretically optimal large-scale solution. Instead, we should choose an approach that balances simplicity and performance.

A naive implementation could become inefficient if it repeatedly explores all possible paths. However, since edge weights are positive, shortest path algorithms such as Dijkstra's Algorithm work very well.

Several edge cases are worth considering upfront:

No path exists: we must return -1.
Disconnected graph: some nodes may never be reachable.
Graph updates: newly added edges may create shorter routes.
Single-node reachability: when node1 == node2, the shortest path cost should be 0.
Multiple alternative routes: we must choose the minimum total weight, not the fewest edges.
Dense graph: since the graph can contain nearly all possible directed edges, adjacency representation matters.

Because edge weights are strictly positive (>= 1), Dijkstra's algorithm is guaranteed to work correctly.

Approaches

Brute Force Approach

A brute force solution would try to enumerate every possible path from node1 to node2 using Depth First Search (DFS) or Breadth First Search (BFS).

The idea is simple:

Start from node1.
Explore every reachable path.
Keep track of the cumulative path cost.
Return the minimum cost encountered.

This approach is correct because it eventually examines all valid paths, ensuring the minimum cost path is found.

However, it is extremely inefficient. In a graph with many nodes and edges, the number of possible paths can grow exponentially. Since cycles may exist, careful bookkeeping is required to avoid infinite recursion.

In the worst case, brute force path enumeration becomes prohibitively expensive.

Optimal Approach, Dijkstra's Algorithm with Adjacency List

The key observation is that:

All edge weights are positive.
We repeatedly need shortest path queries.

Positive edge weights make Dijkstra's Algorithm the natural choice.

Instead of exploring all paths, Dijkstra greedily expands the currently cheapest node. A priority queue (min heap) ensures we always process the next node with the smallest known distance.

We store the graph as an adjacency list because:

Adding edges becomes efficient.
Neighbor traversal is fast.
Space usage is proportional to the number of edges.

When shortestPath(node1, node2) is called:

Start Dijkstra from node1.
Use a min heap to prioritize smaller path costs.
Relax neighboring edges.
Stop early once node2 is reached.

Since n <= 100, this solution is easily fast enough.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(V)	Explores every possible path
Optimal	O((V + E) log V) per query	O(V + E)	Dijkstra using adjacency list and min heap

Algorithm Walkthrough

Optimal Algorithm, Dijkstra with Min Heap

Initialize the graph representation

Store the graph as an adjacency list.

Each node maps to a list of:

(neighbor, edgeCost)

This makes traversing outgoing edges efficient. 2. Build the initial graph

During construction, iterate through edges and add each edge into the adjacency list.

Example:

[0,1,2]

becomes:

graph[0].append((1,2))

Handle edge insertion

When addEdge() is called:

Extract from, to, and cost
Append the edge directly into the adjacency list

Since the problem guarantees no duplicate edges, we do not need validation logic. 4. Start shortest path search

When shortestPath(node1, node2) is called:

Create a min heap initialized with:

(0, node1)

This represents reaching the source node at cost 0. 5. Track best known distances

Maintain a distance array:

dist[node]

initialized to infinity.

Set:

dist[node1] = 0

This prevents repeatedly revisiting nodes with worse costs. 6. Process nodes in increasing cost order

Repeatedly pop the smallest distance entry from the heap.

If we already found a shorter route to that node, skip it.

This lazy deletion approach avoids expensive heap updates. 7. Early termination

If the current node equals node2, immediately return the cost.

Since Dijkstra processes nodes in increasing distance order, the first time we pop node2, we have already found the optimal answer. 8. Relax neighboring edges

For every outgoing edge:

current -> neighbor

compute:

newCost = currentCost + edgeWeight

If this improves the best known distance:

Update dist[neighbor]
Push the new state into the heap

Handle unreachable nodes

If the heap becomes empty before reaching node2, return -1.

Why it works

Dijkstra's algorithm relies on the invariant that once a node is removed from the priority queue, its shortest distance is finalized.

Because all edge weights are positive, any future path reaching that node must be equal or larger in cost. Therefore, when node2 is popped from the heap, we know no shorter path can exist, guaranteeing correctness.

Python Solution

from typing import List
import heapq

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.graph = [[] for _ in range(n)]

        for source, destination, cost in edges:
            self.graph[source].append((destination, cost))

    def addEdge(self, edge: List[int]) -> None:
        source, destination, cost = edge
        self.graph[source].append((destination, cost))

    def shortestPath(self, node1: int, node2: int) -> int:
        if node1 == node2:
            return 0

        n = len(self.graph)
        distances = [float("inf")] * n
        distances[node1] = 0

        min_heap = [(0, node1)]

        while min_heap:
            current_cost, current_node = heapq.heappop(min_heap)

            if current_node == node2:
                return current_cost

            if current_cost > distances[current_node]:
                continue

            for neighbor, edge_cost in self.graph[current_node]:
                new_cost = current_cost + edge_cost

                if new_cost < distances[neighbor]:
                    distances[neighbor] = new_cost
                    heapq.heappush(
                        min_heap,
                        (new_cost, neighbor)
                    )

        return -1

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

The implementation closely follows the algorithm described earlier.

The constructor initializes an adjacency list of size n. Each index stores outgoing edges from that node.

The addEdge() method simply appends the new directed edge to the adjacency list. Since duplicate edges are disallowed by the problem, we do not need replacement logic.

The shortestPath() method runs Dijkstra's algorithm from scratch for each query. A distances array stores the best known cost to each node.

A min heap ensures we always process the node with the smallest known distance first. Whenever we discover a cheaper route to a neighbor, we update its distance and push it into the heap.

The line:

if current_cost > distances[current_node]:
    continue

skips outdated heap entries. This is important because a node may be pushed multiple times with different costs.

Finally, we return -1 if the destination cannot be reached.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type Edge struct {
	to   int
	cost int
}

type State struct {
	cost int
	node int
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].cost < pq[j].cost
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

type Graph struct {
	graph [][]Edge
}

func Constructor(n int, edges [][]int) Graph {
	graph := make([][]Edge, n)

	for _, edge := range edges {
		from := edge[0]
		to := edge[1]
		cost := edge[2]

		graph[from] = append(
			graph[from],
			Edge{to: to, cost: cost},
		)
	}

	return Graph{
		graph: graph,
	}
}

func (this *Graph) AddEdge(edge []int) {
	from := edge[0]
	to := edge[1]
	cost := edge[2]

	this.graph[from] = append(
		this.graph[from],
		Edge{to: to, cost: cost},
	)
}

func (this *Graph) ShortestPath(
	node1 int,
	node2 int,
) int {

	if node1 == node2 {
		return 0
	}

	n := len(this.graph)

	distances := make([]int, n)
	for i := range distances {
		distances[i] = math.MaxInt32
	}

	distances[node1] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, State{
		cost: 0,
		node: node1,
	})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(State)

		currentCost := current.cost
		currentNode := current.node

		if currentNode == node2 {
			return currentCost
		}

		if currentCost > distances[currentNode] {
			continue
		}

		for _, edge := range this.graph[currentNode] {
			newCost := currentCost + edge.cost

			if newCost < distances[edge.to] {
				distances[edge.to] = newCost

				heap.Push(pq, State{
					cost: newCost,
					node: edge.to,
				})
			}
		}
	}

	return -1
}

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

The Go implementation mirrors the Python solution conceptually, but Go requires explicit priority queue implementation using the container/heap package.

Unlike Python's built in heapq, Go needs a custom heap structure implementing:

Len()
Less()
Swap()
Push()
Pop()

The adjacency list is stored as:

[][]Edge

where each node maintains its outgoing edges.

Go integers are sufficient because the maximum path cost remains safely within integer limits.

Worked Examples

Example 1

Initial graph:

0 -> 2 (5)
0 -> 1 (2)
1 -> 2 (1)
3 -> 0 (3)

Query 1: `shortestPath(3, 2)`

Initial state:

Heap	Distances
`[(0,3)]`	`[∞,∞,∞,0]`

Pop (0,3):

Neighbor:

3 -> 0 (3)

Update:

Heap	Distances
`[(3,0)]`	`[3,∞,∞,0]`

Pop (3,0):

Neighbors:

0 -> 2 (5)
0 -> 1 (2)

Update:

Heap	Distances
`[(5,1),(8,2)]`	`[3,5,8,0]`

Pop (5,1):

Neighbor:

1 -> 2 (1)

Better path found:

5 + 1 = 6

Update:

Heap	Distances
`[(6,2),(8,2)]`	`[3,5,6,0]`

Pop (6,2):

Destination reached.

Answer:

Query 2: `shortestPath(0,3)`

Start from node 0.

No path exists to node 3.

Answer:

-1

Add Edge

[1,3,4]

Updated graph:

1 -> 3 (4)

Query 3: `shortestPath(0,3)`

Possible route:

0 -> 1 -> 3

Cost:

2 + 4 = 6

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O((V + E) log V)	Dijkstra traversal using a min heap
Space	O(V + E)	Adjacency list, heap, and distance array

Each shortest path query runs Dijkstra's algorithm. Every edge may be processed once, and heap operations cost O(log V).

Because n <= 100, performance remains excellent even under maximum constraints.

Test Cases

# Example case
g = Graph(
    4,
    [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
)

assert g.shortestPath(3, 2) == 6  # Example shortest path
assert g.shortestPath(0, 3) == -1  # No path exists

g.addEdge([1, 3, 4])

assert g.shortestPath(0, 3) == 6  # Path enabled after addEdge

# Single node graph
g = Graph(1, [])

assert g.shortestPath(0, 0) == 0  # Same node

# Direct edge
g = Graph(2, [[0, 1, 7]])

assert g.shortestPath(0, 1) == 7  # Single edge path
assert g.shortestPath(1, 0) == -1  # Directed graph

# Multiple paths, choose minimum cost
g = Graph(
    4,
    [
        [0, 1, 10],
        [0, 2, 1],
        [2, 1, 1],
        [1, 3, 2],
        [2, 3, 100]
    ]
)

assert g.shortestPath(0, 3) == 4  # Cheaper indirect path

# Graph becomes connected after addEdge
g = Graph(3, [[0, 1, 5]])

assert g.shortestPath(0, 2) == -1  # Initially disconnected

g.addEdge([1, 2, 3])

assert g.shortestPath(0, 2) == 8  # Path added dynamically

# Dense graph
g = Graph(
    4,
    [
        [0, 1, 1],
        [0, 2, 10],
        [0, 3, 20],
        [1, 2, 1],
        [1, 3, 5],
        [2, 3, 1]
    ]
)

assert g.shortestPath(0, 3) == 3  # Best multi-hop route

# Unreachable node
g = Graph(
    5,
    [[0, 1, 2], [1, 2, 3]]
)

assert g.shortestPath(0, 4) == -1  # Disconnected node

Test	Why
Problem example	Validates expected behavior
Single node graph	Tests `node1 == node2`
Direct edge	Verifies directed graph behavior
Multiple paths	Ensures minimum weighted route chosen
Dynamic edge insertion	Confirms `addEdge()` works
Dense graph	Tests many connections
Unreachable node	Ensures `-1` returned correctly

Edge Cases

Source and destination are the same node

If node1 == node2, the shortest path should be 0.

This case is easy to overlook, especially when no edges exist. A naive implementation might incorrectly return -1 if it never traverses any edges.

Our implementation handles this immediately:

if node1 == node2:
    return 0

This avoids unnecessary computation and guarantees correctness.

No path exists

The graph may be disconnected, meaning there is no valid route from source to destination.

For example:

0 -> 1
2 -> 3

Querying:

shortestPath(0,3)

should return -1.

Our implementation naturally handles this. If Dijkstra exhausts the priority queue without reaching the destination, we return:

return -1

Newly added edges create shorter routes

An important challenge is that the graph changes over time.

A path that was impossible before may become reachable after calling addEdge().

Example:

0 -> 1

Initially:

0 -> 2

is unreachable.

After:

addEdge([1,2,5])

a new route becomes available.

Since we always run Dijkstra on the current adjacency list, the implementation automatically considers newly inserted edges.

Multiple competing paths

The shortest path may not be the one with the fewest edges.

Example:

0 -> 1 (100)
0 -> 2 (1)
2 -> 1 (1)

The optimal route is:

0 -> 2 -> 1

with cost 2, not the direct edge cost 100.

Dijkstra guarantees the minimum weighted path is found because it always expands the currently cheapest partial path first.

LeetCode 2642 - Design Graph With Shortest Path Calculator

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach, Dijkstra's Algorithm with Adjacency List

Algorithm Walkthrough

Optimal Algorithm, Dijkstra with Min Heap

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Query 1: shortestPath(3, 2)

Query 2: shortestPath(0,3)

Add Edge

Query 3: shortestPath(0,3)

Complexity Analysis

Test Cases

Edge Cases

Source and destination are the same node

No path exists

Newly added edges create shorter routes

Multiple competing paths

Query 1: `shortestPath(3, 2)`

Query 2: `shortestPath(0,3)`

Query 3: `shortestPath(0,3)`