LeetCode Solutions Blog

Design Graph With Shortest Path Calculator

Number: 2678

Difficulty: Hard

Paid? No

Companies: Samsung

Problem Description

Design a directed weighted graph that supports dynamic edge addition and can compute the shortest path between two nodes. The graph is initialized with n nodes and a list of edges. It supports:

Initializing with existing edges.
Dynamically adding a new edge.
Querying the minimum cost between two nodes using the sum of edge costs along a valid path (return -1 if no path exists).

Key Insights

Use an adjacency list to represent the graph efficiently for dynamic edge addition.
Use Dijkstra’s algorithm for computing the shortest path from node1 to node2 since the graph has positive weights.
Maintain an efficient priority queue (heap) for Dijkstra to ensure that nodes are processed in order of increasing distance.
Since the maximum nodes (n) is small (<= 100) and there are few queries, recomputing Dijkstra for each query is acceptable.

Space and Time Complexity

Time Complexity: O(E log n) per shortestPath query where E is the number of edges at the time of the query. Space Complexity: O(n + E) since we store the graph as an adjacency list.

Solution

We represent the graph using an adjacency list, where each node maps to a list of (neighbor, edgeCost) pairs. For the shortestPath operation, we implement Dijkstra’s algorithm using a priority queue to process nodes in increasing order of their distance from the starting node. For each query, we compute the minimum distance from node1 to node2. The addEdge operation simply appends the new edge to the appropriate list in the adjacency list.

Code Solutions

# Python solution pseudo-code with line-by-line comments

import heapq

class Graph:
    # Initialize the graph with n nodes and a list of edges.
    def __init__(self, n, edges):
        self.n = n
        # Create an adjacency list for each node.
        self.adj = {i: [] for i in range(n)}
        # Populate the adjacency list with the initial edges.
        for frm, to, cost in edges:
            self.adj[frm].append((to, cost))
    
    # Add a new edge to the graph.
    def addEdge(self, edge):
        frm, to, cost = edge
        # Since no duplicate edge exists, simply append the new edge.
        self.adj[frm].append((to, cost))
    
    # Compute the shortest path from node1 to node2 using Dijkstra's algorithm.
    def shortestPath(self, node1, node2):
        # Create a list of distances and initialize them to infinity.
        distances = [float('inf')] * self.n
        distances[node1] = 0
        # Use a heap as our priority queue: (cost, node)
        heap = [(0, node1)]
        while heap:
            current_cost, node = heapq.heappop(heap)
            # Early exit if we reached the destination.
            if node == node2:
                return current_cost
            # Skip this node if a shorter path to it has already been found.
            if current_cost > distances[node]:
                continue
            # Check all neighbors of the current node.
            for neighbor, edge_cost in self.adj[node]:
                new_cost = current_cost + edge_cost
                # If a new shorter path to the neighbor is found.
                if new_cost < distances[neighbor]:
                    distances[neighbor] = new_cost
                    heapq.heappush(heap, (new_cost, neighbor))
        # If node2 is unreachable, return -1.
        return -1

# Example usage:
# g = Graph(4, [[0,2,5], [0,1,2], [1,2,1], [3,0,3]])
# print(g.shortestPath(3,2))  # Output: 6
# print(g.shortestPath(0,3))  # Output: -1
# g.addEdge([1,3,4])
# print(g.shortestPath(0,3))  # Output: 6