Design Graph With Shortest Path Calculator Solution in C++

Problem Description

Ah, the classic “Design Graph With Shortest Path Calculator” problem! It’s like trying to find the quickest route to the nearest coffee shop in a city where every street is a one-way road, and you have to navigate through a maze of traffic cones and construction workers. You know, the kind of day where you just want to scream, “Why can’t I just teleport?!”

In this problem, you are tasked with designing a graph and calculating the shortest path between two nodes. Imagine you’re planning a road trip, and you want to avoid the scenic route that takes you through every small town and their respective donut shops (as tempting as they may be). Instead, you want the fastest way to get from point A to point B, without getting lost in the labyrinth of side streets.

Code Solution


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

  void addEdge(vector 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 dist(graph.size(), INT_MAX);
    using P = pair;  // (d, u)
    priority_queue, 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>> graph;
};

Approach

The code uses Dijkstra’s algorithm to find the shortest path in a weighted graph. It initializes a distance vector to keep track of the shortest distance from the starting node to all other nodes. A priority queue (min-heap) is used to efficiently retrieve the next node with the smallest distance. As it explores the graph, it updates the distances and pushes neighboring nodes into the queue until it finds the shortest path to the target node.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O((V + E) log V)
Space Complexity	O(V)

Real-World Example

Imagine you’re using a GPS app to navigate through a city. The app needs to calculate the shortest route from your current location to your destination while considering traffic conditions (weights). The algorithm behind the scenes is similar to what we implemented in our code. It finds the quickest way to get you to that coffee shop without detours through every donut shop in town!