Given an undirected weighted graph with V vertices numbered from 0 to V - 1, an edge list, and a source vertex, find the shortest distance from source to every vertex.
Every edge appears as [u, v, weight] and every weight is non-negative. Return -1 for each vertex unreachable from source.
Example 1
Input: V = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]], source = 0
Output: [0,3,1,4,7]
Explanation: Minimum routes from source are 0, 0->2->1, 0->2, 0->2->1->3, and 0->2->1->3->4.
Example 2
Input: V = 4, edges = [[0,1,2],[1,2,3]], source = 0
Output: [0,2,5,-1]
Explanation: Vertex 2 has minimum distance 5 through vertex 1. Vertex 3 is disconnected from source.
Brute Force Approach
Dijkstra’s Algorithm expands the shortest-path region from the source. With non-negative edge weights, the unsettled vertex having the smallest known distance cannot later receive a shorter path through another unsettled vertex.
A distance array stores the best discovered costs, while a settled array records finalized vertices. Linear minimum selection preserves the greedy logic but scans all vertices repeatedly.
Algorithm
Build an undirected weighted adjacency list, storing every edge in both directions with the corresponding weight.
Initialize all distances as infinity, all settled states as false, and the source distance as
0.Repeat up to
Vtimes and scan all vertices to select the unsettled vertex having the smallest current distance.
End processing when no selectable vertex exists or the smallest distance is infinity, since all remaining vertices are unreachable.
Mark the selected vertex as settled because non-negative weights guarantee finality of the smallest available distance.
Examine every adjacent edge and update the neighbor distance when
distance[current]+weightproduces a smaller value.Replace remaining infinity values with
-1and return the distance array, explicitly identifying unreachable vertices.
Dry Run
dijkstra-algorithm-heading-corrected
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return shortest distances with linear minimum selection. vector<long long> dijkstra(int V, vector<vector<int>>& edges, int source) { vector<vector<pair<int, int>>> adj(V); // 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(V, INF); vector<int> settled(V, 0); // Set the source distance to zero. dist[source] = 0; // Settle at most one vertex during each pass. for (int pass = 0; pass < V; pass++) { int node = -1; // Find the unsettled vertex with minimum distance. for (int vertex = 0; vertex < V; vertex++) { if (!settled[vertex] && (node == -1 || dist[vertex] < dist[node])) { node = vertex; } } // Stop after all reachable vertices are settled. if (node == -1 || dist[node] == INF) { break; } // Finalize the selected shortest distance. settled[node] = 1; // Relax every edge leaving the selected vertex. for (const auto& [neighbor, weight] : adj[node]) { long long candidate = dist[node] + weight; // Update only unsettled neighbors with shorter distance. if (!settled[neighbor] && candidate < dist[neighbor]) { dist[neighbor] = candidate; } } } vector<long long> answer(V, -1); // Convert finite distances to the required answer format. for (int vertex = 0; vertex < V; vertex++) { if (dist[vertex] != INF) { answer[vertex] = dist[vertex]; } } // Return all shortest distances. return answer; }};// Driver code.int main() { int V = 5; vector<vector<int>> edges = { {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3} }; int source = 0; Solution sol; vector<long long> answer = sol.dijkstra(V, edges, source); // Print every shortest distance. for (long long distance : answer) { cout << distance << " "; } return 0;}Complexity Analysis
Time Complexity: O(V²+E), where V and E are the numbers of vertices and edges; minimum selection costs O(V²) and edge relaxation costs O(E).
Space Complexity: O(V+E), where the adjacency list stores V vertices and 2E edge entries, while the distance and settled arrays require O(V) space.
Optimal Approach
The greedy shortest-path rule remains unchanged, but a binary min-heap replaces repeated linear minimum selection. The heap keeps the vertex having the smallest discovered distance at the top.
Every successful relaxation inserts a new distance–vertex pair. Older entries remain in the heap and are skipped when the stored distance no longer matches the latest distance array value.
Algorithm
Build an undirected weighted adjacency list, storing both directions of every edge with the corresponding weight.
Initialize all distances as infinity, set the source distance to
0, and insert{0, source}into a min-heap.Continue processing while the heap contains entries and remove the pair having the smallest distance.
Skip the removed pair when the heap distance differs from the current stored distance, as the pair represents an outdated route.
Examine every adjacent edge and calculate the candidate distance as
currentDistance+edgeWeight.When the candidate distance is smaller, update the neighbor distance and insert the new distance–neighbor pair into the heap.
Replace remaining infinity values with
-1after the heap becomes empty and return the distance array.
Dry Run
dijkstra-algorithm-clean-verified
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return shortest distances with a binary min-heap. vector<long long> dijkstra(int V, vector<vector<int>>& edges, int source) { vector<vector<pair<int, int>>> adj(V); // 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(V, INF); priority_queue< pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>> > minHeap; // Seed the heap with the source vertex. dist[source] = 0; minHeap.push({0, source}); // Process available vertices by smallest known distance. while (!minHeap.empty()) { auto [currentDistance, node] = minHeap.top(); minHeap.pop(); // Ignore an entry replaced by a shorter route. if (currentDistance != dist[node]) { continue; } // Relax every edge leaving the selected vertex. for (const auto& [neighbor, weight] : adj[node]) { long long candidate = currentDistance + weight; // Record a shorter route. if (candidate < dist[neighbor]) { dist[neighbor] = candidate; minHeap.push({candidate, neighbor}); } } } vector<long long> answer(V, -1); // Convert finite distances to the required answer format. for (int vertex = 0; vertex < V; vertex++) { if (dist[vertex] != INF) { answer[vertex] = dist[vertex]; } } // Return all shortest distances. return answer; }};// Driver code.int main() { int V = 5; vector<vector<int>> edges = { {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3} }; int source = 0; Solution sol; vector<long long> answer = sol.dijkstra(V, edges, source); // Print every shortest distance. for (long long distance : answer) { cout << distance << " "; } return 0;}Complexity Analysis
Time Complexity: O((V+E)×log E), where V and E are the numbers of vertices and edges; lazy deletion can retain up to O(E) heap entries. For standard simple graphs, E=O(V²), so log E=O(log V) and the bound is commonly written as O((V+E)×log V).
Space Complexity: O(V+E), where the adjacency list stores graph edges, the distance array stores V values, and the lazy-deletion heap can contain O(E) entries.
Interview follow-up Questions
No. A negative edge can invalidate a distance already treated as minimum. Bellman-Ford Algorithm handles graphs containing negative edges.
Be the first to add a comment.