You are given a weighted undirected graph having n vertices numbered from 1 to n and m edges along with their weights. Find the shortest weight path between the vertex 1 and the vertex n, if there exists a path, and return a list of integers whose first element is the weight of the path, and the rest consist of the nodes on that path. If no path exists, then return a list containing a single element -1.
The input list of edges is as follows - {a, b, w}, denoting there is an edge between a and b, and w is the weight of that edge.
Note: The driver code here will first check if the weight of the path returned is equal to the sum of the weights along the nodes on that path, if equal it will output the weight of the path, else -2. In case the list contains only a single element (-1) it will simply output -1
Input: n = 5, m = 6, edges = [[1, 2, 2], [2, 5, 5], [2, 3, 4], [1, 4, 1], [4, 3, 3], [3, 5, 1]]
Output: 5
Explanation: Shortest path from 1 to n is by the path 1 4 3 5 whose weight is 5
Input: n = 2, m = 1, edges = [[1, 2, 2]]
Output: 2
Explanation: Shortest path from 1 to 2 is by the path 1 2 whose weight is 2
Input: n = 2, m = 0, edges = [ ]
Output: -1
Explanation: Since there are no edges, so no answer is possible
2 <= n <= 10^6
0 <= m <= 10^6
1 <= a, b <= n
1 <= w <= 10^5
Approach : Using Dijkstra Algorithm
class ShortestPath {
using P = pair<int, int> ;
vector<vector<P>> adjList;
vector<int> dijkstra(int n) {
vector<int> parent(n + 1, -1), minDistance(n + 1, INT_MAX);
minDistance[1] = 0;
priority_queue<P, vector<P>, greater<P>> minHeap;
minHeap.push({0, 1}); // Start from the source
while(!minHeap.empty()) {
auto [currDistance, node] = minHeap.top(); minHeap.pop();
if(node == n)
break; // If reached the destination
for(auto& [neighbor, edgeWeight] : adjList[node]) {
int newDistance = currDistance + edgeWeight;
if(minDistance[neighbor] > newDistance) {
minDistance[neighbor] = newDistance;
parent[neighbor] = node;
minHeap.push({newDistance, neighbor});
}
}
}
if(minDistance[n] == INT_MAX)
return {-1}; // If its impossible to reach destination
// Store the nodes of path from n to 1
vector<int> path;
int node = n;
while(node != -1) {
path.push_back(node);
node = parent[node];
}
path.push_back(minDistance[n]); // Store weight of the path
reverse(begin(path), end(path)); // Reverse to get the original order
return path;
}
public:
// O(MLogN) & O(N+M)
vector<int> shortestPath(int n, int m, vector<vector<int>>& edges) {
adjList.resize(n + 1);
for(auto& edge : edges) { // Construct the graph
int u = edge[0];
int v = edge[1];
int w = edge[2];
adjList[u].push_back({v, w});
adjList[v].push_back({u, w});
}
return dijkstra(n);
}
};Note: I originally solved this problem on another coding platform, and the constraints and inputs provided in this are derived from there. However, due to LeetCode guidelines, I cannot link to the original post.
𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍