DSA Dijkstra’s Algorithm

DSA Dijkstra’s Algorithm

(Concept • Steps • Example • Code • Complexity • When to Use)

Dijkstra’s Algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights.
It’s one of the most asked graph algorithms in DSA interviews.

1️⃣ What Problem Does Dijkstra Solve?

Given:

A weighted graph (directed or undirected)
No negative edge weights
A source vertex

Find:

The minimum distance from the source to every other vertex

2️⃣ When to Use Dijkstra (Very Important)

Graph Type	Use Dijkstra?
Unweighted graph	❌ (Use BFS)
Weighted, all weights ≥ 0	✅
Negative edge weights	❌ (Use Bellman–Ford)
DAG	❌ (Use Topo + Relaxation)

3️⃣ Core Idea (Greedy)

Keep a distance array
Start with dist[source] = 0
Repeatedly pick the unvisited node with the smallest distance
Relax its edges (try to improve neighbors’ distances)

“Once the shortest distance to a node is finalized, it never changes.”

4️⃣ Key Terms

Relaxation:
If dist[u] + weight(u,v) < dist[v], update dist[v]
Min-Heap / Priority Queue:
Efficiently get the closest unvisited node

5️⃣ Step-by-Step Example

Graph (weights in brackets)

Source = 0

Initial

After-processing 0

After- processing 2

After-processing 3

Final Distances

6️⃣ Dijkstra Algorithm (Steps)

Initialize dist[] with ∞
Set dist[source] = 0
Push (0, source) into min-heap
While heap not empty:
- Pop node with minimum distance
- Relax all adjacent edges
End

7️⃣ C++ Implementation (Using Priority Queue)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void dijkstra(int src, vector<pair<int,int>> adj[], int V) {
vector<int> dist(V, 1e9);

// min-heap: (distance, node)
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

dist[src] = 0;
pq.push({0, src});

while(!pq.empty()) {
int node = pq.top().second;
int d = pq.top().first;
pq.pop();

if(d > dist[node]) continue;

for(auto edge : adj[node]) {
int next = edge.first;
int weight = edge.second;

if(dist[node] + weight < dist[next]) {
dist[next] = dist[node] + weight;
pq.push({dist[next], next});
}
}
}

// Print result
for(int i = 0; i < V; i++)
cout << "Distance from " << src << " to " << i << " = " << dist[i] << endl;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

void dijkstra(int src, vector<pair<int,int>> adj[], int V) {

vector<int> dist(V, 1e9);

// min-heap: (distance, node)

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

dist[src] = 0;

pq.push({0, src});

while(!pq.empty()) {

int node = pq.top().second;

int d = pq.top().first;

pq.pop();

if(d > dist[node]) continue;

for(auto edge : adj[node]) {

int next = edge.first;

int weight = edge.second;

if(dist[node] + weight < dist[next]) {

dist[next] = dist[node] + weight;

pq.push({dist[next], next});

}

// Print result

for(int i = 0; i < V; i++)

cout << "Distance from " << src << " to " << i << " = " << dist[i] << endl;

}

8️⃣ Graph Representation Used

Adjacency List with weights:

9️⃣ Time & Space Complexity

Time

With min-heap:

Space

🔟 Why Dijkstra Fails with Negative Weights

Dijkstra assumes:

“The shortest distance to a visited node is final.”

Negative edges can break this assumption, giving wrong results.

Use Bellman–Ford if negative edges exist.

1️⃣1️⃣ Dijkstra vs Other Algorithms

Algorithm	Weights	Complexity	Use Case
BFS	Unweighted	O(V+E)	Simple shortest path
Dijkstra	≥ 0	O(E log V)	Fast weighted paths
Bellman-Ford	Any	O(VE)	Negative edges
Floyd-Warshall	Any	O(V³)	All-pairs

1️⃣2️⃣ Real-Life Applications

✔ Google Maps & GPS
✔ Network routing (OSPF)
✔ Game AI pathfinding
✔ Logistics & supply chains
✔ Recommendation systems

Interview Questions (Dijkstra)

Q1. Can Dijkstra handle negative weights?
👉 ❌ No

Q2. Why priority queue is used?
👉 To get minimum distance node efficiently

Q3. Time complexity with min-heap?
👉 O((V+E) log V)

Q4. Difference between BFS and Dijkstra?
👉 BFS for unweighted, Dijkstra for weighted graphs

Final Summary

✔ Dijkstra finds shortest path from one source
✔ Works only with non-negative weights
✔ Uses greedy approach + priority queue
✔ Time complexity: O((V+E) log V)
✔ Extremely important for DSA interviews

DSA Dijkstra’s Algorithm