Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n.
Each edge appears as [u, v, weight] and every weight is positive. Return a list containing the total shortest-path weight first, followed by path vertices from 1 to n. Return [-1] if no path exists.
Example 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,1,4,3,5]
Explanation: Path 1->4->3->5 has total weight 1+3+1=5, which is minimum.
Example 2
Input: n = 2, m = 0, edges = []
Output: [-1]
Explanation: Vertex 2 is unreachable from vertex 1.
Approach
Dijkstra’s Algorithm finds minimum distances from vertex 1 by repeatedly processing the smallest available distance. A min-heap provides efficient minimum selection, while an adjacency list supports traversal of weighted edges.
A parent array records the predecessor responsible for every successful relaxation. After reaching vertex N, following parent links backward constructs the shortest route from N to 1, and reversal restores the forward path order.
Algorithm
Build an undirected weighted adjacency list by storing every edge in both directions with the corresponding weight.
Initialize all distances as infinity, set
parent[i]=ifor every vertex, assigndist[1]=0, and insert{0, 1}into a min-heap.Continue processing while the heap contains entries and remove the distance–vertex pair having the smallest distance.
Skip the removed entry when the heap distance differs from
dist[current], as the entry represents an outdated route.For every adjacent edge, calculate
dist[current]+weight; upon finding a smaller distance, update the neighbor’s distance, assigncurrentas the parent, and insert the updated pair.Return
[-1]whendist[N]remains infinity after heap processing, indicating that no path connects vertices1andN.Follow parent links from
Nback to1, reverse the collected vertices, prependdist[N], and return the shortest distance followed by the path.
Dry Run
print-shortest-path-dijkstra-parent-array-corrected
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return shortest weight followed by the path from 1 to n. vector<long long> shortestPath(int n, int m, vector<vector<int>>& edges) { vector<vector<pair<int, int>>> adj(n + 1); // Build an undirected weighted adjacency list. for (const vector<int>& edge : edges) { int u = edge[0]; int v = edge[1]; int weight = edge[2]; adj[u].push_back({v, weight}); adj[v].push_back({u, weight}); } const long long INF = numeric_limits<long long>::max() / 4; vector<long long> dist(n + 1, INF); vector<int> parent(n + 1); // Initialize every vertex as its own parent. for (int vertex = 1; vertex <= n; vertex++) { parent[vertex] = vertex; } priority_queue< pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>> > minHeap; // Start Dijkstra traversal from vertex 1. dist[1] = 0; minHeap.push({0, 1}); // Process vertices in increasing known distance. while (!minHeap.empty()) { auto [currentDistance, node] = minHeap.top(); minHeap.pop(); // Skip an outdated heap entry. if (currentDistance != dist[node]) { continue; } // Stop after destination distance becomes final. if (node == n) { break; } // Relax every edge leaving the selected vertex. for (const auto& [neighbor, weight] : adj[node]) { long long candidate = currentDistance + weight; // Record a better distance and predecessor. if (candidate < dist[neighbor]) { dist[neighbor] = candidate; parent[neighbor] = node; minHeap.push({candidate, neighbor}); } } } // Return failure after an unreachable destination. if (dist[n] == INF) { return {-1}; } vector<long long> path; int node = n; // Follow predecessor links from destination to source. while (parent[node] != node) { path.push_back(node); node = parent[node]; } path.push_back(1); // Reverse path into source-to-destination order. reverse(path.begin(), path.end()); vector<long long> answer; // Store shortest weight first. answer.push_back(dist[n]); // Store path vertices after the weight. answer.insert(answer.end(), path.begin(), path.end()); return answer; }};// Driver code.int main() { int n = 5; int m = 6; vector<vector<int>> edges = { {1, 2, 2}, {2, 5, 5}, {2, 3, 4}, {1, 4, 1}, {4, 3, 3}, {3, 5, 1} }; Solution sol; vector<long long> answer = sol.shortestPath(n, m, edges); // Print shortest weight followed by path vertices. for (long long value : answer) { cout << value << " "; } return 0;}Complexity Analysis
Time Complexity: O((N+M)×log N), where N and M are the numbers of vertices and edges; heap operations process relaxations and path reconstruction requires at most O(N) time.
Space Complexity: O(N+M), where the adjacency list stores N vertices and 2M edge entries, while the distance, parent, heap, and path storage require O(N+M) space.
Interview follow-up Questions
Yes. Any path carrying minimum total weight is valid unless a tie-breaking rule is specified.
Be the first to add a comment.