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.

Solution

Method 1 – Dijkstra's Algorithm with Adjacency List

Intuition

To efficiently find the shortest path in a directed weighted graph, we use Dijkstra's algorithm. This algorithm explores nodes in order of increasing path cost, always expanding the least costly path first. By maintaining an adjacency list, we can quickly access neighbors and update path costs as we traverse the graph.

Approach

Store the graph as an adjacency list, where each node maps to a list of (neighbor, cost) pairs.
For shortestPath, use a min-heap to always expand the node with the lowest current cost.
Track the minimum cost to reach each node using a distance array or map.
When adding an edge, update the adjacency list.
If the destination is reached, return the cost; if not reachable, return -1.

Complexity

⏰ Time complexity: O(E log V), where E is the number of edges and V is the number of nodes, due to heap operations in Dijkstra's algorithm.
🧺 Space complexity: O(E + V), for storing the adjacency list and heap.

Code

[{"language":"C++","code":"#include <vector>\n#include <queue>\n#include <unordered_map>\nusing namespace std;\nclass Graph {\n    vector<vector<pair<int, int>>> adj;\npublic:\n    Graph(int n, vector<vector<int>>& edges) {\n        adj.resize(n);\n        for (auto& e : edges) adj[e[0]].emplace_back(e[1], e[2]);\n    }\n    void addEdge(vector<int> edge) {\n        adj[edge[0]].emplace_back(edge[1], edge[2]);\n    }\n    int shortestPath(int node1, int node2) {\n        vector<int> dist(adj.size(), INT_MAX);\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;\n        dist[node1] = 0;\n        pq.emplace(0, node1);\n        while (!

Related Tags