Algorithms/Bellman Ford

خوارزمية بِلمان فورد Bellman-Ford هي إحدى خوارزميات إيجاد شجرة المسار الأقصر، وتتميز عن خوارزمية ديكسترا Dijkstra بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة، إلى جانب أنّ خوارزمية بِلمان-فورد أبسط من خوارزمية ديكسترا وهي ملائمة للأنظمة الموزّعة. ولكن ما يعيب هذه الخوارزمية هو أنّ التعقيد الزمني لها هو O(VE)‎ وهو أعلى من التعقيد الزمني لخوارزمية ديكسترا.

خطوات عمل الخوارزمية

يمكن تقسيم الخوارزمية إلى الخطوات التالية:

المدخلات: الرسم البياني والرأس المصدر src.

المخرجات: المسافة الأقصر بين المصدر وجميع الرؤوس في الرسم البياني. إن كانت هناك دورة وزن سالبة negative weight cycle لن تحسب الخوارزمية المسافات الأقصر، بل ستبلّغ عن وجود دورة وزن سالب.

1- الخطوة الأولى هي تهيئة المسافات التي تفصل بين جميع الرؤوس والرأس المصدر لتحمل القيمة ما لانهاية، والمسافة التي تفصل بين المصدر ونفسه لتكون صفرًا. ننشئ المصفوفة dist[]‎ ذات الحجم |V| وتكون جميع القيم فيها هي ما لا نهاية باستثناء العنصر dist[src]‎ الذي سيكون الرأس المصدر.

2- تحسب هذه الخطوة المسافات الأقصر. تُنفّذ الخطوات التالية ‎|V|-1‎ مرة (|V| هو عدد الرؤوس في الرسم البياني المعطى.

a. يُنفّذ ما يلي لكل ضلع u-v:
إن كان dist[v] > dist[u] + weight، نحدّث القيمة dist[v]‎ لتصبح:

dist[v] = dist[u] + weight للضلع uv

3- تبلّغ هذه الخطوة عن وجود دورة وزن سالب في الرسم البياني، وتنفّذ ما يلي لكل ضلع u-v:
إن كانت dist[v] > dist[u] + weight فهذا يعني وجود دورة وزن سالب في الرسم البياني.

تضمن الخطوة الثانية حساب أقصر المسافات إن لم يحتو الرسم البياني على دورة وزن سالب. ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب، وهذا هو الهدف من الخطوة الثالثة.

تحسب الخوارزمية المسارات الأقصر من الأسفل إلى الأعلى، إذ تحسب في البداية المسارات الأقصر والتي تمتلك ضلعًا واحدًا في المسار على الأكثر، ثم تحسب الخوارزمية المسارات الأقصر التي تمتلك ضلعين على الأكثر، وهكذا دواليك. وبعد الدورة i للحلقة التكرارية الخارجية، تحسب الخوارزمية المسارات الأقصر التي تمتلك i ضلع على الأكثر. إن أقصى عدد من الأضلاع التي يمكن أن تكون موجودة في أي مسار بسيط هو ‎|V|-1 ضلع، ولهذا السبب تعمل الحلقة الخارجية ‎|v|-1‎ مرة.

هذا يعني أنّه لو فرضنا عدم وجود دورة وزن سالبة في الرسم البياني، فإن حسبنا المسارات الأقصر التي تمتلك i من الأضلاع على الأكثر، فإنّ المرور على جميع الأضلاع يعني ضمان إعطاء مسار أقصر يمتلك على الأكثر i+1 من الأضلاع.

يمكن توضيح خطوات الخوارزمية باستخدام المخطط التالي:

ليكن الرأس المصدر صفرًا، سنهيّئ جميع المسافات لتكون ما لا نهاية، باستثناء مسافة المصدر. لما كان عدد الرؤوس الكلي في الرسم البياني هو 5، فإنّ جميع الأضلاع ستعالج 4 مرّات.

لنفترض أنّ جميع الأضلاع ستعالج بالترتيب التالي: ‎(B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D)‎. سنحصل على المسافات التالية عند معالجة جميع الأضلاع للمرة الأولى.

يعرض الصف الأول في الصورة المسافات الابتدائية، ويعرض الصف الثاني المسافات الناتجة عن معالجة الأضلاع (B, E) و (D,B) و (B,D) و (A,B)، ويعرض الصف الثالث المسافات عند معالجة الضلع (A,C)، ويعرض الصف الرابع المسافات عند معالجة الأضلاع (D,C) و (B,C) و (E,D).

تضمن الدورة الأولى إعطاء جميع المسارات الأقصر والتي يكون طولها ضلعًا واحدًا على الأكثر.

تؤدي معالجة جميع الأضلاع للمرة الثانية إلى الحصول على المسافات التالية (يعرض الصف الأخير القيم النهائية).

تضمن الدورة الثانية إعطاء جميع المسارات الأقصر والتي يكون طولها ضلعين على الأكثر. ثم تعالج الخوارزمية جميع الأضلاع مرتين إضافيتين، وتُقلّص المسافات بعد الدورة الثانية؛ لذا لا تحدّث الدورتان الثالثة والرابعة قيم المسافات.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية بِلمان-فورد في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 

// تمثيل ضلع موزون في الرسم البياني
struct Edge 
{ 
	int src, dest, weight; 
}; 

// تمثيل رسم بياني متصل وموجّه وموزون
struct Graph 
{ 
	// V -> عدد الرؤوس
	// E -> عدد الأضلاع	
	int V, E; 

	// يُمثّل الرسم البياني كمصفوفة من الأضلاع	
	struct Edge* edge; 
}; 

// إنشاء رسم بياني يمتلك الرؤوس والأضلاع المعطاة
struct Graph* createGraph(int V, int E) 
{ 
	struct Graph* graph = new Graph; 
	graph->V = V; 
	graph->E = E; 
	graph->edge = new Edge[E]; 
	return graph; 
} 

// دالة مساعدة لطباعة الحلّ
void printArr(int dist[], int n) 
{ 
	printf("Vertex Distance from Source\n"); 
	for (int i = 0; i < n; ++i) 
		printf("%d \t\t %d\n", i, dist[i]); 
} 

// الدالة الرئيسية التي تستخدم للعثور على المسافات الأقصر من المصدر
// إلى جميع الرؤوس باستخدام خوارزمية بِلمان-فورد. تكشف الدالة كذلك
// عن دورة الوزن السالب في الرسم البياني
void BellmanFord(struct Graph* graph, int src) 
{ 
	int V = graph->V; 
	int E = graph->E; 
	int dist[V]; 

	// الخطوة الأولى هي تهيئة المسافات التي تفصل بين المصدر
	// وجميع الرؤوس في الرسم البياني لتكون ما لا نهاية	
	for (int i = 0; i < V; i++) 
		dist[i] = INT_MAX; 
	dist[src] = 0; 

	// الخطوة الثانية: إطلاق جميع الأضلاع.
	// يمكن للمسار الأقصر البسيط من المصدر إلى أي عقدة أن يمتلك
	// |V| -1 ضلعًا
	for (int i = 1; i <= V-1; i++) 
	{ 
		for (int j = 0; j < E; j++) 
		{ 
			int u = graph->edge[j].src; 
			int v = graph->edge[j].dest; 
			int weight = graph->edge[j].weight; 
			if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
				dist[v] = dist[u] + weight; 
		} 
	} 

	// تضمن الخطوة الثانية حساب أقصر المسافات
	// إن لم يحتو الرسم البياني على دورة وزن سالب.
	// ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر
	// لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب 
	for (int i = 0; i < E; i++) 
	{ 
		int u = graph->edge[i].src; 
		int v = graph->edge[i].dest; 
		int weight = graph->edge[i].weight; 
		if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
			printf("Graph contains negative weight cycle"); 
	} 

	printArr(dist, V); 

	return; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	/* إنشاء الرسم البياني في الشكل أعلاه */
	int V = 5; // عدد الرؤوس في الرسم البياني
	int E = 8; // عدد الأضلاع في الرسم البياني
	struct Graph* graph = createGraph(V, E); 

	// إضافة الضلع 1-0
	graph->edge[0].src = 0; 
	graph->edge[0].dest = 1; 
	graph->edge[0].weight = -1; 

	// إضافة الضلع 2-0
	graph->edge[1].src = 0; 
	graph->edge[1].dest = 2; 
	graph->edge[1].weight = 4; 

	// إضافة الضلع 2-1
	graph->edge[2].src = 1; 
	graph->edge[2].dest = 2; 
	graph->edge[2].weight = 3; 

	// إضافة الضلع 3-1
	graph->edge[3].src = 1; 
	graph->edge[3].dest = 3; 
	graph->edge[3].weight = 2; 

	// إضافة الضلع 4-1
	graph->edge[4].src = 1; 
	graph->edge[4].dest = 4; 
	graph->edge[4].weight = 2; 

	// إضافة الضلع 2-3
	graph->edge[5].src = 3; 
	graph->edge[5].dest = 2; 
	graph->edge[5].weight = 5; 

	// إضافة الضلع 1-3
	graph->edge[6].src = 3; 
	graph->edge[6].dest = 1; 
	graph->edge[6].weight = 1; 

	// إضافة الضلع 3-4
	graph->edge[7].src = 4; 
	graph->edge[7].dest = 3; 
	graph->edge[7].weight = -3; 

	BellmanFord(graph, 0); 

	return 0; 
}

• بايثون:

# يستخدم هذا الصنف لتمثيل الرسم البياني
class Graph: 

	def __init__(self,vertices): 
		self.V= vertices # عدد الرؤوس
		self.graph = [] # قاموس افتراضي لتخزين الرسم البياني

	# تضيف الدالة ضلعًا إلى الرسم البياني
	def addEdge(self,u,v,w): 
		self.graph.append([u, v, w]) 
		
	# دالة مساعدة لطباعة الحل
	def printArr(self, dist): 
		print("Vertex Distance from Source") 
		for i in range(self.V): 
			print("%d \t\t %d" % (i, dist[i])) 
	
	# الدالة الرئيسية والتي تعثر على المسافات الأقصر التي تفصل
	# المصدر عن جميع الرؤوس باستخدام خوارزمية بِلمان-فورد.
	# تكشف الدالة كذلك عن دورة الوزن السالب.

	def BellmanFord(self, src): 
		
		# الخطوة الأولى هي تهيئة المسافات التي تفصل بين المصدر
		# وجميع الرؤوس في الرسم البياني لتكون ما لا نهاية
		dist = [float("Inf")] * self.V 
		dist[src] = 0

		# الخطوة الثانية: إطلاق جميع الأضلاع.
		# يمكن للمسار الأقصر البسيط من المصدر إلى أي عقدة أن يمتلك
		# |V| -1 ضلعًا
		for i in range(self.V - 1): 
			# تحديث قيمة المسافة وموقع الأب للرؤوس المجاورة
			# للرأس المنتخب. سنأخذ بنظر الاعتبار الرؤوس التي لا تزال موجودة في الرتل فقط.		
			for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						dist[v] = dist[u] + w 

		# تضمن الخطوة الثانية حساب أقصر المسافات
		# إن لم يحتو الرسم البياني على دورة وزن سالب.
		# ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر
		# لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب		

		for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						print "Graph contains negative weight cycle"
						return
						
		# طباعة قيم المسافات كلها
		self.printArr(dist) 

g = Graph(5) 
g.addEdge(0, 1, -1) 
g.addEdge(0, 2, 4) 
g.addEdge(1, 2, 3) 
g.addEdge(1, 3, 2) 
g.addEdge(1, 4, 2) 
g.addEdge(3, 2, 5) 
g.addEdge(3, 1, 1) 
g.addEdge(4, 3, -3) 

# طباعة الحل
g.BellmanFord(0)

• جافا:

// A Java program for Bellman-Ford's single source shortest path 
// algorithm. 
import java.util.*; 
import java.lang.*; 
import java.io.*; 

// تمثيل رسم بياني متصل وموجّه وموزون 
class Graph 
{ 
	// يستخدم هذا الصنف لتمثيل ضلع موزون في الرسم البياني 
	class Edge { 
		int src, dest, weight; 
		Edge() { 
			src = dest = weight = 0; 
		} 
	}; 

	int V, E; 
	Edge edge[]; 

	// إنشاء رسم بياني يمتلك الرؤوس والأضلاع المعطاة 
	Graph(int v, int e) 
	{ 
		V = v; 
		E = e; 
		edge = new Edge[e]; 
		for (int i=0; i<e; ++i) 
			edge[i] = new Edge(); 
	} 

	// الدالة الرئيسية التي تستخدم للعثور على المسافات الأقصر من المصدر
	// إلى جميع الرؤوس باستخدام خوارزمية بِلمان-فورد. تكشف الدالة كذلك
	// عن دورة الوزن السالب في الرسم البياني 
	void BellmanFord(Graph graph,int src) 
	{ 
		int V = graph.V, E = graph.E; 
		int dist[] = new int[V]; 

	// الخطوة الأولى هي تهيئة المسافات التي تفصل بين المصدر
	// وجميع الرؤوس في الرسم البياني لتكون ما لا نهاية	
		for (int i=0; i<V; ++i) 
			dist[i] = Integer.MAX_VALUE; 
		dist[src] = 0; 

	// الخطوة الثانية: إطلاق جميع الأضلاع.
	// يمكن للمسار الأقصر البسيط من المصدر إلى أي عقدة أن يمتلك
	// |V| -1 ضلعًا 
		for (int i=1; i<V; ++i) 
		{ 
			for (int j=0; j<E; ++j) 
			{ 
				int u = graph.edge[j].src; 
				int v = graph.edge[j].dest; 
				int weight = graph.edge[j].weight; 
				if (dist[u]!=Integer.MAX_VALUE && 
					dist[u]+weight<dist[v]) 
					dist[v]=dist[u]+weight; 
			} 
		} 

	// تضمن الخطوة الثانية حساب أقصر المسافات
	// إن لم يحتو الرسم البياني على دورة وزن سالب.
	// ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر
	// لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب 
		for (int j=0; j<E; ++j) 
		{ 
			int u = graph.edge[j].src; 
			int v = graph.edge[j].dest; 
			int weight = graph.edge[j].weight; 
			if (dist[u] != Integer.MAX_VALUE && 
				dist[u]+weight < dist[v]) 
			System.out.println("Graph contains negative weight cycle"); 
		} 
		printArr(dist, V); 
	} 

	// دالة مساعدة لطباعة الحل 
	void printArr(int dist[], int V) 
	{ 
		System.out.println("Vertex Distance from Source"); 
		for (int i=0; i<V; ++i) 
			System.out.println(i+"\t\t"+dist[i]); 
	} 

	// اختبار الدوال السابقة
	public static void main(String[] args) 
	{ 
		int V = 5; // عدد الرؤوس في الرسم البياني
		int E = 8; // عدد الأضلاع في الرسم البياني

		Graph graph = new Graph(V, E); 

		// إضافة الضلع 1-0 
		graph.edge[0].src = 0; 
		graph.edge[0].dest = 1; 
		graph.edge[0].weight = -1; 

		// إضافة الضلع 2-0 
		graph.edge[1].src = 0; 
		graph.edge[1].dest = 2; 
		graph.edge[1].weight = 4; 

		// إضافة الضلع 2-1 
		graph.edge[2].src = 1; 
		graph.edge[2].dest = 2; 
		graph.edge[2].weight = 3; 

		// إضافة الضلع 3-1 
		graph.edge[3].src = 1; 
		graph.edge[3].dest = 3; 
		graph.edge[3].weight = 2; 

		// إضافة الضلع 4-1 
		graph.edge[4].src = 1; 
		graph.edge[4].dest = 4; 
		graph.edge[4].weight = 2; 

		// إضافة الضلع 2-3 
		graph.edge[5].src = 3; 
		graph.edge[5].dest = 2; 
		graph.edge[5].weight = 5; 

		// إضافة الضلع 1-3 
		graph.edge[6].src = 3; 
		graph.edge[6].dest = 1; 
		graph.edge[6].weight = 1; 

		// إضافة الضلع 3-4 
		graph.edge[7].src = 4; 
		graph.edge[7].dest = 3; 
		graph.edge[7].weight = -3; 

		graph.BellmanFord(graph, 0); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Vertex   Distance from Source
0                0
1                -1
2                2
3                -2
4                1

ملاحظات:

1. الأضلاع السالبة موجودة في الكثير من تطبيقات الرسوم البيانية، فعلى سبيل المثال، عوضًا عن دفع ثمن معين من أجل مسار ما، يمكن أن نستفيد من السير على ذلك المسار.
2. تؤدي خوارزمية بِلمان-فورد أداءً أفضل (أفضل من خوارزمية ديكسترا) في الأنظمة الموزّعة distributed systems. وعلى العكس من خوارزمية ديكسترا والتي تحتاج إلى العثور على القيمة الصغرى لجميع الرؤوس، فإنّ خوارزمية بِلمان-فورد تمرّ على الأضلاع واحدًا تلو الآخر.

انظر أيضًا

• خوارزمية ديكسترا: تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة.
• خوارزمية فلويد وارشال: تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج.

مصادر

• صفحة Bellman–Ford Algorithm في توثيق الخوارزميات في موقع GeeksforGeeks.