Introduction

In this blog post, we will explore how to solve the LeetCode problem "2642" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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.

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Dijkstra's Algorithm: We'll use Dijkstra's algorithm to find the shortest path between two nodes. Dijkstra's is well-suited for finding the shortest paths from a single source node to all other nodes in a weighted graph.
• Adjacency List Representation: The graph will be represented using an adjacency list (a dictionary where keys are nodes and values are lists of neighbors and edge costs). This provides efficient access to a node's neighbors.

• Lazy Evaluation (Shortest Path Calculation on Demand): The shortest path between two nodes will be calculated only when the shortestPath method is called. This avoids pre-calculating all shortest paths, which would be inefficient given the constraint of at most 100 calls to addEdge and shortestPath.

• Complexity:

  • Runtime: O(E log V) for shortestPath (where E is the number of edges and V is the number of vertices) due to Dijkstra's algorithm with a priority queue. O(1) for addEdge. O(V + E) for initialization.
  • Storage: O(V + E) to store the adjacency list.

Code

    import heapq

class Graph:

    def __init__(self, n: int, edges: list[list[int]]):
        self.n = n
        self.adj = [[] for _ in range(n)]
        for u, v, w in edges:
            self.adj[u].append((v, w))

    def addEdge(self, edge: list[int]) -> None:
        u, v, w = edge
        self.adj[u].append((v, w))

    def shortestPath(self, node1: int, node2: int) -> int:
        dist = {node: float('inf') for node in range(self.n)}
        dist[node1] = 0
        pq = [(0, node1)]  # (cost, node)

        while pq:
            cost, u = heapq.heappop(pq)

            if cost > dist[u]:
                continue

            if u == node2:
                return cost

            for v, weight in self.adj[u]:
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    heapq.heappush(pq, (dist[v], v))

        return -1