| Difficulty | Source | Tags | |
|---|---|---|---|
Medium |
160 Days of Problem Solving |
|
The problem can be found at the following link: Question Link
Given an undirected, weighted graph with V vertices numbered from 0 to V-1 and E edges, represented by a 2D array edges[][] (where each edges[i] = [u, v, w] represents an edge between nodes u and v with weight w), find the shortest distance from a given source vertex src to all other vertices.
Return an array of integers where the ith element denotes the shortest distance from the source vertex src to vertex i.
Note: The graph is connected and does not contain any negative weight edge.
Note: Sorry for uploading late, my Final Sem exam is going on.
V = 3
edges[][] = [[0, 1, 1], [1, 2, 3], [0, 2, 6]]
src = 2
[4, 3, 0]
- For vertex 0: The shortest path is
2 -> 1 -> 0with total distance 4. - For vertex 1: The shortest path is
2 -> 1with total distance 3. - For vertex 2: The distance is 0 as it is the source.
V = 5
edges[][] = [[0, 1, 4], [0, 2, 8], [1, 4, 6], [2, 3, 2], [3, 4, 10]]
src = 0
[0, 4, 8, 10, 10]
- For vertex 1: The shortest path is
0 -> 1with total distance 4. - For vertex 2: The shortest path is
0 -> 2with total distance 8. - For vertex 3: The shortest path is
0 -> 2 -> 3with total distance 10. - For vertex 4: The shortest path is
0 -> 1 -> 4with total distance 10.
$1 \leq V \leq 10^4$ $1 ≤ E = edges.size() ≤ 10^5$ $0 ≤ edges[i][j] ≤ 10^4$ $0 \leq src < V$ - Edge weights are non-negative
- Build the Graph: Convert the given edge list into an adjacency list representation.
- Initialize Distances: Set a distance vector
d[]with high values and updated[src] = 0. - Min-Heap (Priority Queue): Use a min-heap to pick the node with the smallest tentative distance.
- Relaxation: For each neighboring vertex, update its distance if a shorter path is found.
- Convert the edges into an adjacency list
g. - Initialize a distance array
dof size V with a large value (e.g.,1e9), and setd[src] = 0. - Push
(0, src)into a min-heap. - While the heap is not empty:
- Pop the top element (with the smallest tentative distance).
- If the current distance is greater than the recorded distance, continue to the next.
- Otherwise, for each adjacent vertex, check if the path through the current vertex gives a smaller distance; update and push the new pair in the heap.
- Return the distance array
das the result.
- Expected Time Complexity: O((V + E) * log V), since each vertex and edge is processed, and insertion/extraction from the heap takes logarithmic time.
- Expected Auxiliary Space Complexity: O(V + E), for the adjacency list and the additional storage used by the heap.
// ✅ Optimized Dijkstra’s Algorithm (Min-Heap + Adjacency List)
class Solution {
public:
vector<int> dijkstra(int V, vector<vector<int>> &edges, int src) {
vector<vector<pair<int, int>>> g(V);
for (auto &e : edges) g[e[0]].emplace_back(e[1], e[2]);
vector<int> d(V, 1e9); d[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.emplace(0, src);
while (!q.empty()) {
auto p = q.top(); q.pop();
if (p.first > d[p.second]) continue;
for (auto &x : g[p.second])
if (p.first + x.second < d[x.first])
q.emplace(d[x.first] = p.first + x.second, x.first);
}
return d;
}
};- Build an adjacency list
gfrom the edges. - Initialize distance array
dwith large values, and setd[src] = 0. - Use a
std::setto mimic a min-priority queue, which maintains sorted order automatically. - At each step, pick the node with the smallest tentative distance.
- For each adjacent node, if a shorter path is found, update and insert the new pair.
class Solution {
public:
vector<int> dijkstra(int V, vector<vector<int>> &edges, int src) {
vector<vector<pair<int, int>>> g(V);
for (auto &e : edges) g[e[0]].emplace_back(e[1], e[2]);
vector<int> d(V, 1e9);
d[src] = 0;
set<pair<int, int>> st;
st.emplace(0, src);
while (!st.empty()) {
pair<int, int> p = *st.begin();
int du = p.first;
int u = p.second;
st.erase(st.begin());
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i].first;
int w = g[u][i].second;
if (du + w < d[v]) {
st.erase({d[v], v});
d[v] = du + w;
st.emplace(d[v], v);
}
}
}
return d;
}
};- Expected Time Complexity: O((V + E) * log V)
- Expected Auxiliary Space Complexity: O(V + E)
- Leverages
std::setto ease decrease-key operations. - Provides more control over updates at the cost of increased insertion/erase overhead compared to the min-heap.
| Approach | ⏱️ Time Complexity | 🗂️ Space Complexity | ✅ Pros | |
|---|---|---|---|---|
| Min-Heap (Priority Queue) | 🟢 O((V + E) * log V) | 🟡 O(V + E) | Fast for sparse graphs, standard implementation | Slightly verbose STL usage |
| Set-Based Approach | 🟡 O((V + E) * log V) | 🟡 O(V + E) | Easy key updates using ordered set | Set operations can be slower than heap push |
✅ Best Choice?
- Min-Heap (Priority Queue): Best for most competitive and real-world graph problems.
- Set-Based Approach: Use when you require more explicit key updates.
class Solution {
public int[] dijkstra(int V, int[][] edges, int src) {
List<int[]>[] g = new List[V];
for (int i = 0; i < V; i++) g[i] = new ArrayList<>();
for (int[] e : edges) g[e[0]].add(new int[]{e[1], e[2]});
int[] d = new int[V];
Arrays.fill(d, Integer.MAX_VALUE);
d[src] = 0;
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
q.offer(new int[]{0, src});
while (!q.isEmpty()) {
int[] p = q.poll();
if (p[0] > d[p[1]]) continue;
for (int[] x : g[p[1]])
if (p[0] + x[1] < d[x[0]])
q.offer(new int[]{d[x[0]] = p[0] + x[1], x[0]});
}
return d;
}
}class Solution:
def dijkstra(self, V, edges, src):
from heapq import heappush, heappop
g = [[] for _ in range(V)]
for u, v, w in edges:
g[u].append((v, w))
d = [float('inf')] * V
d[src] = 0
q = [(0, src)]
while q:
du, u = heappop(q)
if du > d[u]: continue
for v, w in g[u]:
if du + w < d[v]:
d[v] = du + w
heappush(q, (d[v], v))
return dFor discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐