2642. Design Graph With Shortest Path Calculator LeetCode Solution

In this guide, you will get 2642. Design Graph With Shortest Path Calculator LeetCode Solution with the best time and space complexity. The solution to Design Graph With Shortest Path Calculator problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Design Graph With Shortest Path Calculator solution in C++
Design Graph With Shortest Path Calculator solution in Java
Design Graph With Shortest Path Calculator solution in Python
Additional Resources

2642. Design Graph With Shortest Path Calculator LeetCode Solution image

Problem Statement of Design Graph With Shortest Path Calculator

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.

Complexity Analysis

Time Complexity: O((|V| + |E|)\log |V|)
Space Complexity: O(|V| + |E|)

2642. Design Graph With Shortest Path Calculator LeetCode Solution in C++

class Graph {
 public:
  Graph(int n, vector<vector<int>>& edges) {
    graph.resize(n);
    for (const vector<int>& edge : edges)
      addEdge(edge);
  }

  void addEdge(vector<int> edge) {
    const int u = edge[0];
    const int v = edge[1];
    const int w = edge[2];
    graph[u].emplace_back(v, w);
  }

  int shortestPath(int node1, int node2) {
    vector<int> dist(graph.size(), INT_MAX);
    using P = pair<int, int>;  // (d, u)
    priority_queue<P, vector<P>, greater<>> minHeap;

    dist[node1] = 0;
    minHeap.emplace(dist[node1], node1);

    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      if (u == node2)
        return d;
      for (const auto& [v, w] : graph[u])
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.emplace(dist[v], v);
        }
    }

    return -1;
  }

 private:
  vector<vector<pair<int, int>>> graph;
};
/* code provided by PROGIEZ */

2642. Design Graph With Shortest Path Calculator LeetCode Solution in Java

class Graph {
  public Graph(int n, int[][] edges) {
    graph = new List[n];
    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();
    for (int[] edge : edges)
      addEdge(edge);
  }

  public void addEdge(int[] edge) {
    final int u = edge[0];
    final int v = edge[1];
    final int w = edge[2];
    graph[u].add(new Pair<>(v, w));
  }

  public int shortestPath(int node1, int node2) {
    int[] dist = new int[graph.length];
    Arrays.fill(dist, Integer.MAX_VALUE);
    // (d, u)
    Queue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));

    dist[node1] = 0;
    minHeap.offer(new Pair<>(dist[node1], node1));

    while (!minHeap.isEmpty()) {
      final int d = minHeap.peek().getKey();
      final int u = minHeap.poll().getValue();
      if (u == node2)
        return d;
      for (Pair<Integer, Integer> pair : graph[u]) {
        final int v = pair.getKey();
        final int w = pair.getValue();
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.offer(new Pair<>(dist[v], v));
        }
      }
    }

    return -1;
  }

  private List<Pair<Integer, Integer>>[] graph;
}
// code provided by PROGIEZ

2642. Design Graph With Shortest Path Calculator LeetCode Solution in Python

class Graph:
  def __init__(self, n: int, edges: list[list[int]]):
    self.graph = [[] for _ in range(n)]
    for edge in edges:
      self.addEdge(edge)

  def addEdge(self, edge: list[int]):
    u, v, w = edge
    self.graph[u].append((v, w))

  def shortestPath(self, node1: int, node2: int) -> int:
    dist = [math.inf] * len(self.graph)

    dist[node1] = 0
    minHeap = [(dist[node1], node1)]  # (d, u)

    while minHeap:
      d, u = heapq.heappop(minHeap)
      if u == node2:
        return d
      for v, w in self.graph[u]:
        if d + w < dist[v]:
          dist[v] = d + w
          heapq.heappush(minHeap, (dist[v], v))

    return -1
 # code by PROGIEZ