خوارزمية فلويد وارشال

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

المدخلات:
       graph[][] = { {0,   5,  INF, 10},
                    {INF,  0,  3,  INF},
                    {INF, INF, 0,   1},
                    {INF, INF, INF, 0} }

تمثل المدخلات الرسم البياني التالي:

             10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3

لاحظ أنّ القيمة graph[i][j]‎ هي 0 إن كانت i تساوي j، وأنّ قيمة graph[i][j]‎ تساوي INF (ما لا نهاية) إن لم يكن هناك ضلع يربط بين الرأسين i و j.

المخرجات:
Shortest distance matrix
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

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

تبدأ الخوارزمية بتهيئة مصفوفة الحل solution matrix التي تكون مشابهة لمصفوفة الرسم البياني المدخل، ثم تحدّث مصفوفة الحل وذلك باعتبار جميع الرؤوس كرأس وسطي. تنتقي الخوارزمية جميع الرؤوس واحدًا تلو الآخر وتحدث جميع قيم المسارات الأقصر التي تتضمن الرأس المنتخب كرأس وسطي في المسار الأقصر.

عند انتخاب الرأس ذي الرقم k كرأس وسطي، فإنّنا قد عددنا الرؤوس ‎{0, 1, 2, ..k-1}‎ كرؤوس وسطية، ولكل زوج (i, j) لرؤوس المصدر والوجهة على التوالي هناك احتمالان:

1. أن لا يكون k رأسًا وسطيًا في المسار الأقصر الذي يفصل بين i و j؛ لذا نبقي على قيمة dist[i][j]‎ كما هي.
2. أن يكون k رأسًا وسطيًا في المسار الأقصر الذي يفصل بين i و j؛ لذا نحدث قيمة dist[i][j]‎ لتصبح dist[i][k] + disk[k][j]‎ إذا كانت ‎dist[i][j] > dist[i][k] + dist[k][j]‎.

أمثلة

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

• C++:

#include <bits/stdc++.h> 
using namespace std; 

// عدد الرؤوس في الرسم البياني
#define V 4 

/* تعيين قيمة كبيرة لتمثل قيمة ما لا نهاية.
ستستخدم هذه القيمة للرؤوس غير المرتبطة ببعضها البعض */
#define INF 99999 

// تطبع الدالة مصفوفة الحل
void printSolution(int dist[][V]); 

void floydWarshall (int graph[][V]) 
{ 
	/* ستكون المصفوفة أدناه مصفوفة المخرجات والتي ستحتوي
	على المسافات الأقصر بين كل زوج من الرؤوس في الرسم البياني */
	int dist[V][V], i, j, k; 

	
	/* تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.
	أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر
	تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار
	عدم وجود رأس وسطي */
	for (i = 0; i < V; i++) 
		for (j = 0; j < V; j++) 
			dist[i][j] = graph[i][j]; 

	/* إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة
	الرؤوس الوسية.
	---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني
	بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة
	{0, 1, 2, .. k-1}
	كرؤوس وسطية.
	---> بعد انتهاء عمل الحلقة التكرارية
	k يضاف الرأس 
	إلى مجموعة الرؤوس الوسطية وتصبح المجموعة
	{0, 1, 2, .. k}
	*/

	for (k = 0; k < V; k++) 
	{ 
		// اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر
		for (i = 0; i < V; i++) 
		{ 
			// اختيار جميع الرؤوس التي ستكون وجهة للمصدر المنتخب في الخطوة السابقة
			for (j = 0; j < V; j++) 
			{ 
				// إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر
				// بين متغير الحلقة الثانية والثالثة فسنحدث قيمة 
				// dist[i][j]
				if (dist[i][k] + dist[k][j] < dist[i][j]) 
					dist[i][j] = dist[i][k] + dist[k][j]; 
			} 
		} 
	} 

	// طباعة مصفوفة المسافة الأقصر
	printSolution(dist); 
} 

/* دالة مساعدة لطباعة الحل */
void printSolution(int dist[][V]) 
{ 
	cout<<"The following matrix shows the shortest distances"
			" between every pair of vertices \n"; 
	for (int i = 0; i < V; i++) 
	{ 
		for (int j = 0; j < V; j++) 
		{ 
			if (dist[i][j] == INF) 
				cout<<"INF"<<" "; 
			else
				cout<<dist[i][j]<<" "; 
		} 
		cout<<endl; 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	/* إنشاء الرسم البياني الموزون التالي:
			10 
	(0)------->(3) 
		| /|\ 
	5 | | 
		| | 1 
	\|/ | 
	(1)------->(2) 
			3 */
	int graph[V][V] = { {0, 5, INF, 10}, 
						{INF, 0, 3, INF}, 
						{INF, INF, 0, 1}, 
						{INF, INF, INF, 0} 
					}; 

	// طباعة الحل
	floydWarshall(graph); 
	return 0; 
}

• بايثون:

# عدد الرؤوس في الرسم البياني
V = 4

# تعيين قيمة كبيرة لتمثل قيمة ما لا نهاية.
# ستستخدم هذه القيمة للرؤوس غير المرتبطة ببعضها البعض
INF = 99999

def floydWarshall(graph): 

	# ستكون المصفوفة أدناه مصفوفة المخرجات والتي ستحتوي
	# على المسافات الأقصر بين كل زوج من الرؤوس في الرسم البياني
	# تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.
	# أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر
	# تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار
	# عدم وجود رأس وسطي
	
	dist = map(lambda i : map(lambda j : j , i) , graph) 
	
	# إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة
	الرؤوس الوسية.
	# ---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني
	# بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة
	# {0, 1, 2, .. k-1}
	# كرؤوس وسطية.
	# ---> بعد انتهاء عمل الحلقة التكرارية
	# k يضاف الرأس 
	# إلى مجموعة الرؤوس الوسطية وتصبح المجموعة
	# {0, 1, 2, .. k}
	
	for k in range(V): 

		# اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر 
		for i in range(V): 

			# اختيار جميع الرؤوس التي ستكون وجهة 
			# للمصدر المنتخب في الخطوة السابقة 
			for j in range(V): 

				# إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر 
				# بين متغير الحلقة الثانية والثالثة فسنحدث قيمة
				# dist[i][j]
				dist[i][j] = min(dist[i][j] , 
								dist[i][k]+ dist[k][j] 
								) 
	printSolution(dist) 


# دالة مساعدة لطباعة الحل
def printSolution(dist): 
	print "Following matrix shows the shortest distances\ 
between every pair of vertices" 
	for i in range(V): 
		for j in range(V): 
			if(dist[i][j] == INF): 
				print "%7s" %("INF"), 
			else: 
				print "%7d\t" %(dist[i][j]), 
			if j == V-1: 
				print "" 



# اختبار الدوال السابقة
# إنشاء الرسم البياني الموزون التالي
""" 
			10 
	(0)------->(3) 
		|		 /|\ 
	5 |		 | 
		|		 | 1 
	\|/		 | 
	(1)------->(2) 
			3		 """
graph = [[0,5,INF,10], 
			[INF,0,3,INF], 
			[INF, INF, 0, 1], 
			[INF, INF, INF, 0] 
		] 
# طباعة الحل
floydWarshall(graph);

• جافا:

import java.util.*; 
import java.lang.*; 
import java.io.*; 


class AllPairShortestPath 
{ 
	final static int INF = 99999, V = 4; 

	void floydWarshall(int graph[][]) 
	{ 
		int dist[][] = new int[V][V]; 
		int i, j, k; 

		/* تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.
	أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر
	تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار
	عدم وجود رأس وسطي */
		for (i = 0; i < V; i++) 
			for (j = 0; j < V; j++) 
				dist[i][j] = graph[i][j]; 

		/* إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة
	الرؤوس الوسية.
	---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني
	بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة
	{0, 1, 2, .. k-1}
	كرؤوس وسطية.
	---> بعد انتهاء عمل الحلقة التكرارية
	k يضاف الرأس 
	إلى مجموعة الرؤوس الوسطية وتصبح المجموعة
	{0, 1, 2, .. k}
	*/
		for (k = 0; k < V; k++) 
		{ 
			// اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر 
			for (i = 0; i < V; i++) 
			{ 
				// اختيار جميع الرؤوس التي ستكون وجهة للمصدر المنتخب في الخطوة السابقة 
				for (j = 0; j < V; j++) 
				{ 
					// إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر
				// بين متغير الحلقة الثانية والثالثة فسنحدث قيمة 
				// dist[i][j]
					if (dist[i][k] + dist[k][j] < dist[i][j]) 
						dist[i][j] = dist[i][k] + dist[k][j]; 
				} 
			} 
		} 

		// طباعة مصفوفة المسافة الأقصر 
		printSolution(dist); 
	} 

	void printSolution(int dist[][]) 
	{ 
		System.out.println("The following matrix shows the shortest "+ 
						"distances between every pair of vertices"); 
		for (int i=0; i<V; ++i) 
		{ 
			for (int j=0; j<V; ++j) 
			{ 
				if (dist[i][j]==INF) 
					System.out.print("INF "); 
				else
					System.out.print(dist[i][j]+" "); 
			} 
			System.out.println(); 
		} 
	} 

	// اختبار الدوال السابقة
	public static void main (String[] args) 
	{ 
		/* إنشاء الرسم البياني الموزون التالي: 
		10 
		(0)------->(3) 
		|		 /|\ 
		5 |		 | 
		|		 | 1 
		\|/		 | 
		(1)------->(2) 
		3		 */
		int graph[][] = { {0, 5, INF, 10}, 
						{INF, 0, 3, INF}, 
						{INF, INF, 0, 1}, 
						{INF, INF, INF, 0} 
						}; 
		AllPairShortestPath a = new AllPairShortestPath(); 

		// طباعة الحل
		a.floydWarshall(graph); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(V^3)‎.

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

كذلك استخدام القيمة INT_MAX من الترويسة limits.h عوضًا عن القيمة INF وذلك لضمان أنّنا نتعامل مع أكبر قيمة ممكنة، وعند القيام بذلك يجب تعديل عبارة الشرطية في البرنامج أعلاه لتجنب حدوث فيضان حسابي arithmetic overflow.

مصادر

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