← Back to DSA Course | Chapter 13: Graphs | Lesson 7 of 10

Shortest Path यानि Dijkstra Algorithm

Dijkstra का algorithm एक GPS जैसा है जो आपके घर से हर दूसरी जगह तक shortest route ढूंढता है, हमेशा अगला सबसे करीब unvisited जगह visit करते हुए।

In this page:

  1. What is Dijkstra
  2. Relaxation
  3. Non-Negative Weights
  4. Example
  5. Complexity
Syntax
markup 
import heapq
dist = {v: float('inf') for v in graph}
dist[source] = 0
heap = [(0, source)]
while heap:
    d, u = heapq.heappop(heap)
    for v, w in graph[u]:
        if d + w < dist[v]:
            dist[v] = d + w
            heapq.heappush(heap, (dist[v], v))

What is Dijkstra

Dijkstra का algorithm एक starting vertex से हर दूसरे vertex तक shortest distance ढूंढता है, लेकिन सिर्फ तब सही काम करता है जब सभी edge weights zero या positive हों — एक negative edge इसे permanently गलत answer पर settle करा सकता है।

उदाहरण: What is Dijkstra

#include <iostream>
using namespace std;
int main() {
	int weights[] = {4, 2, -1};
	cout << "Weight -1 present: Dijkstra would settle on a wrong shortest distance here";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] weights = {4, 2, -1};
		System.out.println("Weight -1 present: Dijkstra would settle on a wrong shortest distance here");
	}
}
weights = [4, 2, -1]
print("Weight -1 present: Dijkstra would settle on a wrong shortest distance here")
#include <stdio.h>
int main() {
	int weights[] = {4, 2, -1};
	printf("Weight -1 present: Dijkstra would settle on a wrong shortest distance here");
	return 0;
}

Relaxation

किसी edge को relax करने का मतलब है यह जांचना कि इससे होकर जाना किसी vertex तक currently recorded से एक छोटी known distance देता है या नहीं, और अगर हां तो वह distance update करना — पूरे algorithm में repeated होने वाला core operation।

उदाहरण: Relaxation

#include <iostream>
using namespace std;
int main() {
	int dist[] = {0, 10, 1000000};
	int u = 1, v = 2, weight = 3;
	if (dist[u] + weight < dist[v]) {
		cout << "Relax: dist[" << v << "] updated from " << dist[v] << " to " << dist[u]+weight;
		dist[v] = dist[u] + weight;
	}
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] dist = {0, 10, 1000000};
		int u = 1, v = 2, weight = 3;
		if (dist[u] + weight < dist[v]) {
			System.out.println("Relax: dist[" + v + "] updated from " + dist[v] + " to " + (dist[u]+weight));
		}
	}
}
dist = [0, 10, 1000000]
u, v, weight = 1, 2, 3
if dist[u] + weight < dist[v]:
    print(f"Relax: dist[{v}] updated from {dist[v]} to {dist[u]+weight}")
#include <stdio.h>
int main() {
	int dist[] = {0, 10, 1000000};
	int u = 1, v = 2, weight = 3;
	if (dist[u] + weight < dist[v]) printf("Relax: dist[%d] updated from %d to %d", v, dist[v], dist[u]+weight);
	return 0;
}

Non-Negative Weights

Non-negative-weight requirement इसलिए मौजूद है क्योंकि Dijkstra एक बार process होने के बाद किसी vertex की distance permanently finalize करता है, यह मानते हुए कि कोई भविष्य की discovery कभी एक shorter path produce नहीं कर सकती — यह guarantee तुरंत टूट जाती है जैसे ही एक negative edge allowed हो।

उदाहरण: Non-Negative Weights

#include <iostream>
using namespace std;
int main() {
	int finalized = 5;
	cout << "Vertex " << finalized << " finalized: no future edge can ever shorten it since all weights are >= 0";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int finalized = 5;
		System.out.println("Vertex " + finalized + " finalized: no future edge can ever shorten it since all weights are >= 0");
	}
}
finalized = 5
print(f"Vertex {finalized} finalized: no future edge can ever shorten it since all weights are >= 0")
#include <stdio.h>
int main() {
	int finalized = 5;
	printf("Vertex %d finalized: no future edge can ever shorten it since all weights are >= 0", finalized);
	return 0;
}

Example

एक road network की कल्पना करें जहां हर road का एक positive travel time हो: एक city से शुरू करते हुए, Dijkstra हर दूसरी city तक shortest travel time discover करता है हमेशा currently-closest unvisited city से बाहर की ओर expand करके।

उदाहरण: Example

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
	vector<vector<pair<int,int>>> adj = {{{1,4},{2,1}},{{3,1}},{{1,1},{3,5}},{}};
	vector<int> dist(4, 1000000); dist[0] = 0;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
	pq.push({0,0});
	while (!pq.empty()) {
		auto [d,u] = pq.top(); pq.pop();
		if (d > dist[u]) continue;
		for (auto [v,w] : adj[u]) if (dist[u]+w < dist[v]) { dist[v]=dist[u]+w; pq.push({dist[v],v}); }
	}
	cout << "Shortest travel time to city 3: " << dist[3];
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[][][] adj = {{{1,4},{2,1}},{{3,1}},{{1,1},{3,5}},{}};
		int[] dist = {0,1000000,1000000,1000000};
		PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
		pq.add(new int[]{0,0});
		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int d = cur[0], u = cur[1];
			if (d > dist[u]) continue;
			for (int[] edge : adj[u]) {
				int v = edge[0], w = edge[1];
				if (dist[u]+w < dist[v]) { dist[v] = dist[u]+w; pq.add(new int[]{dist[v],v}); }
			}
		}
		System.out.println("Shortest travel time to city 3: " + dist[3]);
	}
}
import heapq
adj = [[(1,4),(2,1)],[(3,1)],[(1,1),(3,5)],[]]
dist = [1000000]*4
dist[0] = 0
pq = [(0,0)]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:
        continue
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq, (dist[v], v))
print("Shortest travel time to city 3:", dist[3])
#include <stdio.h>
int main() {
	int dist[4] = {0, 1000000, 1000000, 1000000};
	int edges[4][3] = {{0,1,4},{0,2,1},{2,1,1},{2,3,5}};
	for (int pass = 0; pass < 3; pass++)
		for (int i = 0; i < 4; i++)
			if (dist[edges[i][0]] + edges[i][2] < dist[edges[i][1]])
				dist[edges[i][1]] = dist[edges[i][0]] + edges[i][2];
	printf("Shortest travel time to city 3: %d", dist[3]);
	return 0;
}

Complexity

अगला-closest vertex हमेशा चुनने के लिए एक min-priority queue उपयोग करना running time को roughly O((V+E) log V) तक लाता है; एक heap के बिना naive array scan O(V²) लेता है, जो छोटे या dense graphs के लिए ठीक है लेकिन बड़े sparse वालों के लिए धीमा है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)");
	}
}
print("Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)")
#include <stdio.h>
int main() {
	printf("Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)");
	return 0;
}
Related Topics

Shortest Path यानि Bellman-Ford Algorithm · Topological Sort क्या है · Cycle Detection कैसे करें · Minimum Spanning Tree यानि Kruskal Algorithm

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Negative weights वाले graph पर Dijkstra चलाना, जो गलत distances दे सकता है।
  2. Distances को INT_MAX initialize करना और फिर इसमें एक weight जोड़ना, जो overflow करता है।
  3. Distance finalize होने के बाद किसी vertex को फिर process करना, या stale queue entries skip करना भूल जाना।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Topological Sort Next Lesson → Shortest Path Bellman-Ford

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.