🌱 Keegan's Digital Garden

2642. Design Graph With Shortest Path Calculator

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- question seems pretty straightfoward
- difficulty lies in:
	1. implementing weights
	2. memorizing how to do dijkstras 
	3. adjusting the algorithm to only return the cost for the shortest path

🤔What Did I Struggle With?

~

💡 Explanation of Solution

See Dijkstra’s Shortest Path Algorithm and Graphs

⌛ Complexity Analysis

Time Complexity: O((V + E) log V)
	- construction of the graph is O() where e is the number of edges in the graph (e is guaranteed to be greater than the number of vertices v)
	- shortest path calculation is O((V + E) log V) since the extraction of the minimum element from the heap is of O(log V)

Space Complexity: O(V + E)

💻 Implementation of Solution

```cpp
class Graph {
private:
    int V;
    vector<list<pair<int,int>>> adjList;
 
public:
    Graph(int n, vector<vector<int>>& edges) {
        this->V = n;
        adjList.resize(n);    
 
        for(auto edge : edges) {
            this->addEdge(edge);
        }
    }
    
    // edge {from, to, edgeCost}
    void addEdge(vector<int> edge) {
        int from = edge[0];
        int to = edge[1];
        int weight = edge[2];
 
        adjList[from].emplace_back(to, weight);
    }
    
    int shortestPath(int node1, int node2) {
        if (node1 == node2) return 0; // Shortest path to itself is 0
 
        vector<int> dist(this->V, numeric_limits<int>::max()); //init distances as infinite
        dist[node1] = 0;
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, node1}); //distance , vertex
 
        while(!pq.empty()) {
            int u = pq.top().second;
            int uDist = pq.top().first;
            pq.pop();
 
            if (uDist > dist[u]) continue; // Skip if distance is outdated
 
            for(auto& neighbor : this->adjList[u]) {
                int v = neighbor.first;
                int weight = neighbor.second;
 
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
 
        // If there is no path to node2, return -1
        return (dist[node2] == numeric_limits<int>::max()) ? -1 : dist[node2];
    }
};

Graph View