We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Graph With Shortest Path Calculator

Difficulty: Hard

Problem Description

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 with methods to initialize the graph, add edges, and calculate the shortest path between two nodes.

Key Insights

  • The problem involves handling a directed graph with weighted edges.
  • We need to implement a method for adding edges dynamically.
  • A shortest path algorithm (like Dijkstra's) is necessary to efficiently find the minimum cost path between two nodes.
  • The graph can have up to 100 nodes and edges, allowing us to use algorithms that may have higher time complexity for shorter input sizes.

Space and Time Complexity

Time Complexity:

  • Adding an edge: O(1)
  • Finding the shortest path: O((E + V) log V) where E is the number of edges and V is the number of nodes (using Dijkstra's algorithm).

Space Complexity:

  • O(V + E) for storing the graph as an adjacency list.

Solution

To solve this problem, we will use an adjacency list to represent the directed graph, which allows efficient edge addition and traversal. For finding the shortest path, we will implement Dijkstra's algorithm using a priority queue (min-heap) to explore the graph.

  1. Graph Representation: Use a dictionary of lists where the key is the node and the value is a list of tuples representing the edges (neighbor, cost).
  2. Adding Edges: Simply append the new edge to the corresponding node's list in the adjacency list.
  3. Shortest Path Calculation: Use a priority queue to keep track of the minimum cost to reach each node and update costs as we traverse through the graph.

Code Solutions

import heapq

class Graph:
    def __init__(self, n: int, edges: list[list[int]]):
        self.graph = {i: [] for i in range(n)}
        for from_node, to_node, cost in edges:
            self.graph[from_node].append((to_node, cost))

    def addEdge(self, edge: list[int]) -> None:
        from_node, to_node, cost = edge
        self.graph[from_node].append((to_node, cost))

    def shortestPath(self, node1: int, node2: int) -> int:
        min_heap = [(0, node1)]  # (cost, node)
        visited = set()
        while min_heap:
            current_cost, current_node = heapq.heappop(min_heap)
            if current_node in visited:
                continue
            visited.add(current_node)
            if current_node == node2:
                return current_cost
            for neighbor, cost in self.graph[current_node]:
                if neighbor not in visited:
                    heapq.heappush(min_heap, (current_cost + cost, neighbor))
        return -1
← Back to All Questions