Shortest Path यानि Bellman-Ford Algorithm

Bellman-Ford एक और route-finding method है, Dijkstra से ज़्यादा patient, और यह उन roads को handle कर सकती है जहां आप tolls चुकाने के बजाय points gain करते हैं।

In this page:

What is Bellman-Ford
Relax Edges
Negative Weights
Negative Cycle
Complexity

Syntax

markup

dist = {v: float('inf') for v in vertices}
dist[source] = 0
for _ in range(len(vertices) - 1):
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

What is Bellman-Ford

Bellman-Ford भी एक single source से shortest paths ढूंढता है, लेकिन Dijkstra के विपरीत यह negative edge weights सहन करता है — तब उपयोगी जब कुछ edges costs के बजाय gains represent करते हैं, जैसे currency arbitrage या refund scenarios।

उदाहरण: What is Bellman-Ford

#include <iostream>
using namespace std;
int main() {
	int edges[][3] = {{0,1,5},{1,2,-3}};
	cout << "Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] edges = {{0,1,5},{1,2,-3}};
		System.out.println("Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not");
	}
}

edges = [(0,1,5),(1,2,-3)]
print("Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not")

#include <stdio.h>
int main() {
	int edges[2][3] = {{0,1,5},{1,2,-3}};
	printf("Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not");
	return 0;
}

Relax Edges

Vertices को greedily finalize करने के बजाय, यह graph के हर single edge को relax करता है, प्रति pass एक बार, shorter paths को कई rounds में धीरे-धीरे propagate होने देते हुए जब तक कोई distance आगे improve न हो सके।

उदाहरण: Relax Edges

#include <iostream>
using namespace std;
int main() {
	int dist[3] = {0, 1000000, 1000000};
	int edges[2][3] = {{0,1,4},{1,2,-2}};
	for (int pass = 0; pass < 2; pass++)
		for (auto& e : edges)
			if (dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
	cout << "After relaxing all edges twice, dist[2] = " << dist[2];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] dist = {0, 1000000, 1000000};
		int[][] edges = {{0,1,4},{1,2,-2}};
		for (int pass = 0; pass < 2; pass++)
			for (int[] e : edges)
				if (dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
		System.out.println("After relaxing all edges twice, dist[2] = " + dist[2]);
	}
}

dist = [0, 1000000, 1000000]
edges = [(0,1,4),(1,2,-2)]
for _ in range(2):
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
print("After relaxing all edges twice, dist[2] =", dist[2])

#include <stdio.h>
int main() {
	int dist[3] = {0, 1000000, 1000000};
	int edges[2][3] = {{0,1,4},{1,2,-2}};
	for (int pass = 0; pass < 2; pass++)
		for (int i = 0; i < 2; 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("After relaxing all edges twice, dist[2] = %d", dist[2]);
	return 0;
}

Negative Weights

चूंकि algorithm कोई weight non-negative मानकर नहीं चलता, यह एक path को सही तरीके से shorten कर सकता है भले ही इसके लिए temporarily एक ऐसी edge उपयोग करनी पड़े जो running total घटाती है।

उदाहरण: Negative Weights

#include <iostream>
using namespace std;
int main() {
	int dist[2] = {0, 10};
	int weight = -7;
	if (dist[0] + weight < dist[1]) { dist[1] = dist[0] + weight; cout << "Shortened via negative edge to " << dist[1]; }
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] dist = {0, 10};
		int weight = -7;
		if (dist[0] + weight < dist[1]) { dist[1] = dist[0] + weight; System.out.println("Shortened via negative edge to " + dist[1]); }
	}
}

dist = [0, 10]
weight = -7
if dist[0] + weight < dist[1]:
    dist[1] = dist[0] + weight
    print("Shortened via negative edge to", dist[1])

#include <stdio.h>
int main() {
	int dist[2] = {0, 10};
	int weight = -7;
	if (dist[0] + weight < dist[1]) { dist[1] = dist[0] + weight; printf("Shortened via negative edge to %d", dist[1]); }
	return 0;
}

Negative Cycle

V vertices वाले एक graph में एक shortest path ज़्यादा से ज़्यादा V-1 edges उपयोग कर सकता है, इसलिए अगर V-1 पूरे passes के बाद भी एक distance improve हो सके, वह improvement सिर्फ एक edge weight से explain हो सकता है जो एक cycle के चारों ओर indefinitely value खोता है — एक negative cycle, जिसे extra pass exposed करता है।

उदाहरण: Negative Cycle

#include <iostream>
using namespace std;
int main() {
	int V = 4;
	bool improvedOnPassV = true;
	if (improvedOnPassV) cout << "Distance still improved after " << V-1 << " passes: negative cycle detected";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int V = 4;
		boolean improvedOnPassV = true;
		if (improvedOnPassV) System.out.println("Distance still improved after " + (V-1) + " passes: negative cycle detected");
	}
}

V = 4
improved_on_pass_v = True
if improved_on_pass_v:
    print(f"Distance still improved after {V-1} passes: negative cycle detected")

#include <stdio.h>
int main() {
	int V = 4;
	int improvedOnPassV = 1;
	if (improvedOnPassV) printf("Distance still improved after %d passes: negative cycle detected", V-1);
	return 0;
}

Complexity

हर edge को एक बार relax करने में O(E) time लगता है, और algorithm इसे ज़्यादा से ज़्यादा V-1 passes के लिए दोहराता है, overall O(VE) देते हुए — Dijkstra के algorithm से धीमा, लेकिन negative weights को सुरक्षित रूप से handle करने की कीमत।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely");
	}
}

print("Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely")

#include <stdio.h>
int main() {
	printf("Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely");
	return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Shortest Path Dijkstra Next Lesson → Minimum Spanning Tree Kruskal