خوارزمية ديكسترا

من موسوعة حسوب

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

تشبه خوارزمية ديكسترا في عملها إلى حدٍّ كبير خوارزمية برم Prim لإيجاد الشجرة الممتدة الصغرى.

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

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

  1. إنشاء مجموعة (ليكن اسمها sptSet) لمتابعة الرؤوس الموجودة في شجرة المسار الأقصر، أي الرؤوس التي قد تمّ حساب مسافتها الصغرى من المصدر. وتكون هذه المجموعة فارغة في البداية.
  2. إسناد قيمة للمسافة إلى جميع الرؤوس في الرسم البياني المدخل، ثم تهيئة جميع قيم المسافات لتكون ما لا نهاية INFINITE وإسناد القيمة 0 للرأس المصدر لكي يكون أول رأس تختاره الخوارزمية.
  3. إنشاء حلقة تكرارية شرطها عدم وجود جميع الرؤوس في مجموعة sptSet وتؤدي هذه الحلقة الخطوات التالية:
    1. اختيار أحد الرؤوس u من الرسم البياني بشرط أن لا يكون موجودًا في المجموعة sptSet ويمتلك قيمة للمسافة الصغرى.
    2. إضافة u إلى المجموعة sptSet.
    3. تحديث قيمة المسافة لجميع الرؤوس المجاورة للرأس u، وللقيام بذلك نمرّ على جميع الرؤوس المجاورة، ولكل رأس مجاور v، إذا كان مجموعة قيمة المسافة للرأس u (من المصدر) ووزن الضلع u-v أقل من قيمة مسافة الرأس v، فسنحدث حينئذٍ قيمة المسافة للرأس v.

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

تكون المجموعة sptSet فارغة في البداية، وتكون قيم المسافات المسندة إلى الرؤوس في الرسم البياني هي ‎{0, INF, INF, INF, INF, INF, INF, INF}‎ (ترمز INF إلى ما لا نهاية). والآن نختار الرؤاس الذي يمتلك أصغر قيمة للمسافة، وهو الرأس 0، ونضيفه إلى المجموعة sptSet؛ وبهذا تصبح المجموعة {0}.

بعد إضافة الرأس 0 إلى المجموعة sptSet نجري تحديثًا لقيم المسافة للرؤوس المجاورة له، وهما الرأسان 1 و 7، والذان ستحدّث قيمة المسافة لهما إلى 4 و 8. يعرض الشكل التالي الرؤوس التي تمتلك قيم مسافة محددة فقط، والرؤوس الموجودة في شجرة المسار الأقصر SPT ملوّنة باللون الأحمر.

الخطوة التالية هي اختيار الرأس الذي يمتلك أقل قيمة للمسافة بشرط أن لا يكون موجودًا في شجرة المسار الأقصر (غير موجود في المجموعة sptSet)، وبهذا يتم اختيار الرأس 1 ويضاف إلى المجموعة sptSet، وبذلك تصبح هذه المجموعة ‎{0, 1}‎، ثم نحدّث قيم المسافة للرؤوس المجاورة للرأس 1؛ وبهذا تحدّث قيمة المسافة للرأس 2 إلى القيمة 12.

الخطوة التالية هي اختيار الرأس الذي يمتلك أقل قيمة للمسافة بشرط أن لا يكون موجودًا في شجرة المسار الأقصر (غير موجود في المجموعة sptSet)، وبهذا يتم اختيار الرأس 7 ويضاف إلى المجموعة sptSet، وبذلك تصبح هذه المجموعة ‎{0, 1, 7}‎، ثم نحدّث قيم المسافة للرؤوس المجاورة للرأس 7؛ وبهذا تحدّث قيمة المسافة للرأسين 6 و 8 إلى القيمتين 15 و 9 على التوالي.

الخطوة التالية هي اختيار الرأس الذي يمتلك أقل قيمة للمسافة بشرط أن لا يكون موجودًا في شجرة المسار الأقصر (غير موجود في المجموعة sptSet)، وبهذا يتم اختيار الرأس 6 ويضاف إلى المجموعة sptSet، وبذلك تصبح هذه المجموعة ‎{0, 1, 7, 6}‎، ثم نحدّث قيم المسافة للرؤوس المجاورة للرأس 6؛ وبهذا تحدّث قيمة المسافة للرأسين 5 و 8.

تُكرَّر الخطوات السابقة إلى أن يتحقّق شرط وجود جميع الرؤوس في المجموعة sptSet، وحينها نحصل على شجرة المسار الأقصر.

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

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

تستخدم الأمثلة التالية المصفوفة المنطقية sptSet[]‎ لتمثيل مجموعة الرؤوس المضافة إلى شجرة المسار الأقصر. إن كانت القيمة sptSet[v]‎ قيمة صحيحة فإنّ الرأس v مضاف إلى شجرة المسار الأقصر، وإلا فلا. كذلك تستخدم المصفوفة dist[]‎ لتخزين قيم المسافات الأقصر لجميع الرؤوس في الرسم البياني.

  • C++‎:
#include <stdio.h> 
#include <limits.h> 

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

// دالة مساعدة عملها العثور على الرأس الذي يمتلك أصغر قيمة للمسافة
// في مجموعة الرؤوس غير المضافة بعد إلى شجرة المسار الأقصر


int minDistance(int dist[], bool sptSet[]) 
{ 
// تهيئة القيمة الصغرى
int min = INT_MAX, min_index; 

for (int v = 0; v < V; v++) 
	if (sptSet[v] == false && dist[v] <= min) 
		min = dist[v], min_index = v; 

return min_index; 
} 

// دالة مساعدة لطباعة مصفوفة المسافات
int printSolution(int dist[], int n) 
{ 
printf("Vertex Distance from Source\n"); 
for (int i = 0; i < V; i++) 
	printf("%d tt %d\n", i, dist[i]); 
} 


// الدالة التي تنفذ خوارزمية ديكسترا لإيجاد المسار الأقصر من مصدر واحد
// في الرسم البياني المعطى والممثّل بواسطة مصفوفة المجاورة

void dijkstra(int graph[V][V], int src) 
{ 
	// مصفوفة المخرجات.
	// يمثل العنصر
	// dist[i]
	// i المسار الأقصر من المصدر إلى
	int dist[V];
	
	// ستكون القيمة
	// sptSet[i] 
	// i إن كان الرأس
	// موجودًا في 	
	// sptSet[i] will be true if vertex i is included in shortest 
	// path tree or shortest distance from src to i is finalized 
	bool sptSet[V];
	// Initialize all distances as INFINITE and stpSet[] as false 
	for (int i = 0; i < V; i++) 
		dist[i] = INT_MAX, sptSet[i] = false; 
	
	// تكون المسافة التي تفصل الرأس المصدر عن نفسه صفرًا دائمًا
	dist[src] = 0; 

	// إيجاد المسار الأقصر لجميع الرؤوس
	for (int count = 0; count < V-1; count++) 
	{ 
	
	// اختيار الرأس ذي المسافة الأقصر من مجموعة الرؤوس التي لم تُعالج بعد.
	// في الدورة الأولى تكون
	// u == src
	int u = minDistance(dist, sptSet); 
	
	// تعليم الرأس المنتخب على أنّه معالج
	// Mark the picked vertex as processed 
	sptSet[u] = true; 

	// تحديث قيمة المسافة للرؤوس المجاورة للرأس المنتخب	
	for (int v = 0; v < V; v++) 

		// Update dist[v] only if is not in sptSet, there is an edge from 
		// u to v, and total weight of path from src to v through u is 
		// smaller than current value of dist[v] 
		if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
									&& dist[u]+graph[u][v] < dist[v]) 
			dist[v] = dist[u] + graph[u][v]; 
	} 

	// طباعة مصفوفة المسافات التي تم إنشاؤها
	printSolution(dist, V); 
} 

// اختبار الدوال السابقة 
int main() 
{ 
/* إنشاء الرسم البياني الوارد في المثال أعلاه */
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
					{4, 0, 8, 0, 0, 0, 0, 11, 0}, 
					{0, 8, 0, 7, 0, 4, 0, 0, 2}, 
					{0, 0, 7, 0, 9, 14, 0, 0, 0}, 
					{0, 0, 0, 9, 0, 10, 0, 0, 0}, 
					{0, 0, 4, 14, 10, 0, 2, 0, 0}, 
					{0, 0, 0, 0, 0, 2, 0, 1, 6}, 
					{8, 11, 0, 0, 0, 0, 1, 0, 7}, 
					{0, 0, 2, 0, 0, 0, 6, 7, 0} 
					}; 

	dijkstra(graph, 0); 

	return 0; 
}
  • بايثون:
import sys 

class Graph(): 

	def __init__(self, vertices): 
		self.V = vertices 
		self.graph = [[0 for column in range(vertices)] 
					for row in range(vertices)] 
	
	def printSolution(self, dist): 
		print "Vertex tDistance from Source"
		for node in range(self.V): 
			print node,"t",dist[node] 
	
	# دالة مساعدة للعثور على الرأس
    # ذي قيمة المسافة الأقصر، من مجموعة الرؤوس
    # التي لم تضف بعد إلى شجرة المسار
	def minDistance(self, dist, sptSet): 
	
		# تهيئة المسافة الأقصر من العقدة التالية
		min = sys.maxsize
	
		# البحث عن أقرب رأس غير موجود في شجرة المسار الأقصر
		for v in range(self.V): 
			if dist[v] < min and sptSet[v] == False: 
				min = dist[v] 
				min_index = v 
	
		return min_index 
	
	# دالة لتنفيذ خوارزمية ديكسترا أحادية المصدر
    # لإيجاد المسار الأقصر لرسم بياني ممثل
    # باستخدام مصفوفة المجاورة
	def dijkstra(self, src): 
	
		dist = [sys.maxsize] * self.V 
		dist[src] = 0
		sptSet = [False] * self.V 
	
		for cout in range(self.V): 
			
            # اختيار المسافة الأقصر من مجموعة
            # الرؤوس التي لم تعالج بعد
            # في الدورة الأولى تكون
            # u == src
			u = self.minDistance(dist, sptSet) 
	
			# وضع الرأس ذي المسافة الأقصر في شجرة المسار الأقصر	
			sptSet[u] = True
	
			# تحديث قيمة المسافة للرؤوس المجاورة
        	# للرأس المنتخب بشرط أن تكون المسافة الحالية
            # أكبر من المسافة الجديدة وأن الرأس
            # غير موجود في شجرة المسار الأقصر
			for v in range(self.V): 
				if self.graph[u][v] > 0 and sptSet[v] == False and
				dist[v] > dist[u] + self.graph[u][v]: 
						dist[v] = dist[u] + self.graph[u][v] 
	
		self.printSolution(dist) 

# اختبار الدوال السابقة
g = Graph(9) 
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], 
		[4, 0, 8, 0, 0, 0, 0, 11, 0], 
		[0, 8, 0, 7, 0, 4, 0, 0, 2], 
		[0, 0, 7, 0, 9, 14, 0, 0, 0], 
		[0, 0, 0, 9, 0, 10, 0, 0, 0], 
		[0, 0, 4, 14, 10, 0, 2, 0, 0], 
		[0, 0, 0, 0, 0, 2, 0, 1, 6], 
		[8, 11, 0, 0, 0, 0, 1, 0, 7], 
		[0, 0, 2, 0, 0, 0, 6, 7, 0] 
		]; 

g.dijkstra(0);
  • جافا:
import java.util.*; 
import java.lang.*; 
import java.io.*; 

class ShortestPath 
{ 
	// دالة مساعدة للعثور على الرأس الذي يمتلك أقل قيمة للمسافة
    // في مجموعة الرؤوس التي لم تضف بعد إلى شجرة المسار الأقصر
	static final int V=9; 
	int minDistance(int dist[], Boolean sptSet[]) 
	{ 
		// تهيئة القيمة الدنيا 
		int min = Integer.MAX_VALUE, min_index=-1; 

		for (int v = 0; v < V; v++) 
			if (sptSet[v] == false && dist[v] <= min) 
			{ 
				min = dist[v]; 
				min_index = v; 
			} 
	
		return min_index; 
	} 
	
	// دالة مساعدة لطباعة المصفوفة التي تم إنشاؤها
	void printSolution(int dist[], int n) 
	{ 
		System.out.println("Vertex Distance from Source"); 
		for (int i = 0; i < V; i++) 
			System.out.println(i+" tt "+dist[i]); 
	} 
	
	// تنفّذ الدالة خوارزمية دكسترا أحادية المصدر للعثور على
    // المسار الأقصر في رسم بياني ممثّل بواسطة مصفوفة المجاورة
	void dijkstra(int graph[][], int src) 
	{ 
		// مصفوفة المخرجات.
		// يمثل العنصر
		// dist[i]
		// i المسار الأقصر من المصدر إلى
 
		int dist[] = new int[V];
        
		// sptSet[i] will true if vertex i is included in shortest 
		// path tree or shortest distance from src to i is finalized 
		Boolean sptSet[] = new Boolean[V]; 
	
		// Initialize all distances as INFINITE and stpSet[] as false 
		for (int i = 0; i < V; i++) 
		{ 
			dist[i] = Integer.MAX_VALUE; 
			sptSet[i] = false; 
		} 
	
		// تكون المسافة بين الرأس المصدر ونفسه صفرًا دائمًا
		dist[src] = 0; 
	
		// العثور على المسار الأقصر لجميع الرؤوس
		for (int count = 0; count < V-1; count++) 
		{ 
			// اختيار الرأس ذي المسافة الأقصر من مجموعة الرؤوس التي لم تُعالج بعد.
			// في الدورة الأولى تكون
			// u == src 
			int u = minDistance(dist, sptSet); 
	
			// تعليم الرأس المنتخب على أنّه معالج
			sptSet[u] = true; 
	
			// تحديث قيمة المسافة للرؤوس المجاورة للرأس المنتخب
			for (int v = 0; v < V; v++) 
	
				// Update dist[v] only if is not in sptSet, there is an 
				// edge from u to v, and total weight of path from src to 
				// v through u is smaller than current value of dist[v] 
				if (!sptSet[v] && graph[u][v]!=0 && 
						dist[u] != Integer.MAX_VALUE && 
						dist[u]+graph[u][v] < dist[v]) 
					dist[v] = dist[u] + graph[u][v]; 
		} 
	
		// طباعة المصفوفة التي تم إنشاؤها
		printSolution(dist, V); 
	} 
	
	// اختبار الدوال السابقة 
	public static void main (String[] args) 
	{ 
		/* إنشاء الرسم البياني الوارد في المثال أعلاه */
	int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
								{4, 0, 8, 0, 0, 0, 0, 11, 0}, 
								{0, 8, 0, 7, 0, 4, 0, 0, 2}, 
								{0, 0, 7, 0, 9, 14, 0, 0, 0}, 
								{0, 0, 0, 9, 0, 10, 0, 0, 0}, 
								{0, 0, 4, 14, 10, 0, 2, 0, 0}, 
								{0, 0, 0, 0, 0, 2, 0, 1, 6}, 
								{8, 11, 0, 0, 0, 0, 1, 0, 7}, 
								{0, 0, 2, 0, 0, 0, 6, 7, 0} 
								}; 
		ShortestPath t = new ShortestPath(); 
		t.dijkstra(graph, 0); 
	} 
}

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

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14

ملاحظات:

  1. تحسب الشيفرة المسافة الأقصر، ولكنّها لا تحسب المعلومات المرتبطة بالمسار، ولكن يمكن استخدام مصفوفة أبوية parent array وتحديثها عند تحديث المسافة واستخدامها لعرض المسار الأقصر من مصدر معين إلى رؤوس مختلفة.
  2. تعمل هذه الشيفرة على الرسوم البيانية غير الموجّهة، ولكن يمكن استخدام الدالة نفسها مع الرسوم البيانية الموجّهة.
  3. تعثر الشيفرة على المسافة الأقصر بين مصدر معين وجميع الرؤوس في الرسم البياني. إن كان المطلوب العثور على المسافة التي تربط بين مصدر معين وبين رأس واحد فقط، يمكن قطع الحلقة التكرارية عندما يكون الرأس المنتخب مساويًا للهدف المطلوب. (الخطوة 3.1 في خطوات الخوارزمية أعلاه).
  4. لا يمكن استخدام خوارزمية ديكسترا مع الرسوم البيانية التي تكون أوزان أضلاعها ذات قيم سالبة، ولكن يمكن استخدام خوارزمية بيلمان-فورد في مثل هذه الحالة.

الرسوم البيانية الممثلة بواسطة قائمة المجاورة

إذا استخدمت قائمة المجاورة لتمثيل الرسم البياني فإن من الممكن التنقل عبر جميع الرؤوس في الرسم البياني باستخدام خوارزمية البحث بالعرض أولًا Breadth First Search وبتعقيد زمني قدره O(V+E)‎.

تتنقل هذه الطريقة عبر جميع الرؤوس في الرسم البياني باستخدام خورازمية البحث بالعرض أولًا، وتستخدم الكومة الصغرى Min Heap لتخزين الرؤوس غير المضافة بعد إلى شجرة المسار الأقصر SPT (أو الرؤوس التي لم تُحسب المسافة الأقصر لها بعد). تستخدم الكومة الصغرى كرتل أولوية priority queue للحصول على الرأس ذي المسافة الأقصر من مجموعة الرؤوس غير المضافة بعد إلى شجرة المسار الأقصر. ويؤدي كل ذلك إلى تخفيض التعقيد الزمني لهذه العملية إلى O(Log V)‎.

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

  1. إنشاء كومة صغرى حجمها V، وتمثّل V عدد الرؤوس الموجودة في الرسم البياني المعطى. تحتوي كل عقدة في الكومة الصغرى على رقم الرأس وقيمة المسافة لذلك الرأس.
  2. تهيئة الكومة الصغرى باستخدام رأس مصدري كجذر للكومة، وتكون قيمة المسافة المسندة إلى الرأس المصدر هي 0 أما قيمة المسافة المسندة إلى بقية الرؤوس فتكون INF (ما لانهاية).
  3. تؤدي الخوارزمية ما يلي بشرط أن لا تكون الكومة الصغرى فارغة:
    1. استخراج الرأس الذي يمتلك أصغر قيمة للمسافة من الكومة الصغرى، وليكن u.
    2. لكل رأس مجاور (ليكن v) للرأس u، يجري التحقق من أنّ v موجود في الكومة الصغرى. فإن كان كذلك، وكانت قيمة المسافة أكبر من وزن الضلع u-v مضافةً إليه قيمة المسافة للرأس u، فسنحدث قيمة المسافة للرأس v.

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

ليكن الرأس المصدر هو 0.

في البدء تكون قيمة المسافة للرأس المصدر هي 0 وتكون INF (ما لا نهاية) لبقية الرؤوس في الرسم البياني. لذا فإنّ الرأس المصدر سيُستخرج من الكومة الصغرى وسُتحدّث قيمة المسافة للرؤوس المجاورة للرأس 0 (وهما 1 و 7). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرأس 0.

الرؤوس الملونة باللون الأحمر هي الرؤوس التي تم الانتهاء من حساب قيمة المسافة الصغرى لها وهي خارج الكومة الصغرى.

لما كانت قيمة المسافة للرأس 1 هي الأصغر من بين جميع العقد في الكومة الصغرى، فإنّها ستُستخرج من الكومة وستُحدث قمية المسافة للرؤوس المجاورة للرأس 1 (تحدث قيمة المسافة إن كان الرأس غير موجود في الكومة الصغرى وكانت المسافة عبر الرأس 1 أقصر من المسافة السابقة). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرأسين 0 و 1.

لما كانت قيمة المسافة للرأس 7 هي الأصغر من بين جميع العقد في الكومة الصغرى، فإنّها ستُستخرج من الكومة وستحدث قيمة المسافة للرؤوس المجاورة (هما الرأسان 6 و 8). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرؤوس ‎0, 1, 7.

لما كانت قيمة المسافة للرأس 6 هي الأصغر من بين جميع العقد في الكومة الصغرى، فإنّها ستُستخرج من الكومة وستحدث قيمة المسافة للرؤوس المجاورة (هما الرأسان 5 و 8). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرؤوس ‎0, 1, 7, 6‎.


تُكرّر الخطوات السابقة إلى أن تصبح الكومة فارغة، ونحصل في النهاية على شجرة المسار الأقصر:

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

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

  • C++‎:
#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 

// تمثيل العقدة في قائمة المجاورة
struct AdjListNode 
{ 
	int dest; 
	int weight; 
	struct AdjListNode* next; 
}; 

// تمثيل عقدة المجاورة 
struct AdjList 
{ 
	struct AdjListNode *head; // مؤشر إلى عدة الرأس في القائمة
}; 


// تمثيل الرسم البياني. الرسم البياني هو مصفوفة من قوائم المجاورة
// V حجم المصفوفة سيكون
// (عدد الرؤوس في الرسم البياني)
struct Graph 
{ 
	int V; 
	struct AdjList* array; 
}; 

// دالة مساعدة لإنشاء عقدة قائمة مجاورة جديدة
struct AdjListNode* newAdjListNode(int dest, int weight) 
{ 
	struct AdjListNode* newNode = 
			(struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
	newNode->dest = dest; 
	newNode->weight = weight; 
	newNode->next = NULL; 
	return newNode; 
} 

// دالة مساعدة لإنشاء الرسم البياني يضم العدد المعطى من الرؤوس
struct Graph* createGraph(int V) 
{ 
	struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); 
	graph->V = V; 

    // V إنشاء مصفوفة لقائمة المجاورة، وسيكون حجم المصفوفة
	graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

	// NULL تهيئة كل قائمة مجاورة لتكون فارغة وذلك بإعطاء الرأس القيمة 
	for (int i = 0; i < V; ++i) 
		graph->array[i].head = NULL; 

	return graph; 
} 

// تضيف الدالة ضلعًا إلى الرسم البياني غير الموجّه
void addEdge(struct Graph* graph, int src, int dest, int weight) 
{ 
	// إضافة ضلع من المصدر إلى الوجهة. تضاف عقدة جديدة إلى قائمة المجاورة الخاصة بالمصدر
    // تضاف العقدة في البداية
	struct AdjListNode* newNode = newAdjListNode(dest, weight); 
	newNode->next = graph->array[src].head; 
	graph->array[src].head = newNode; 

	// لما كان الرسم البياني غير موجّه، فإن الضلع سيضاف من الوجهة إلى المصدر أيضًا
    // Since graph is undirected, add an edge from dest to src also 
	newNode = newAdjListNode(src, weight); 
	newNode->next = graph->array[dest].head; 
	graph->array[dest].head = newNode; 
} 

// تمثيل عقدة في الكومة الصغرى
struct MinHeapNode 
{ 
	int v; 
	int dist; 
}; 

// تمثيل الكومة الصغرى
struct MinHeap 
{ 
	int size;	 // عدد عقد الكومة الموجودة حاليًا
	int capacity; // سعة الكومة الصغرى
	int *pos;	 //  decreaseKey() مطلوب من قبل الدالة
	struct MinHeapNode **array; 
}; 

// دال ةمساعدة لإنشاء عقدة كومة صغرى جديدة
struct MinHeapNode* newMinHeapNode(int v, int dist) 
{ 
	struct MinHeapNode* minHeapNode = 
		(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode)); 
	minHeapNode->v = v; 
	minHeapNode->dist = dist; 
	return minHeapNode; 
} 

// دالة مساعدة لإنشاء كومة صغرى
struct MinHeap* createMinHeap(int capacity) 
{ 
	struct MinHeap* minHeap = 
		(struct MinHeap*) malloc(sizeof(struct MinHeap)); 
	minHeap->pos = (int *)malloc(capacity * sizeof(int)); 
	minHeap->size = 0; 
	minHeap->capacity = capacity; 
	minHeap->array = 
		(struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*)); 
	return minHeap; 
} 

// دالة مساعدة للتبديل بين عقدتين في الكومة الصغرى
// تحتاج عملية التحويل إلى كومة إلى عملية التبديل هذه
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) 
{ 
	struct MinHeapNode* t = *a; 
	*a = *b; 
	*b = t; 
} 

// دالة قياسية لإنشاء الكومة باستخدام الموقع المعطى
// تحدث هذه الدالة كذلك موقع العقد عند التبديل بينها
// decreaseKey() الموقع مطلوب من قبل الدالة
void minHeapify(struct MinHeap* minHeap, int idx) 
{ 
	int smallest, left, right; 
	smallest = idx; 
	left = 2 * idx + 1; 
	right = 2 * idx + 2; 

	if (left < minHeap->size && 
		minHeap->array[left]->dist < minHeap->array[smallest]->dist ) 
	smallest = left; 

	if (right < minHeap->size && 
		minHeap->array[right]->dist < minHeap->array[smallest]->dist ) 
	smallest = right; 

	if (smallest != idx) 
	{ 
		// العقد التي تحتاج إلى تبديل في الكومة الصغرى
		MinHeapNode *smallestNode = minHeap->array[smallest]; 
		MinHeapNode *idxNode = minHeap->array[idx]; 

		// تبديل المواقع
		minHeap->pos[smallestNode->v] = idx; 
		minHeap->pos[idxNode->v] = smallest; 

		// تبديل العقد
		swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); 

		minHeapify(minHeap, smallest); 
	} 
} 

// دالة مساعدة للتحقق من أنّ الكومة الصغرى فارغة أو لا
int isEmpty(struct MinHeap* minHeap) 
{ 
	return minHeap->size == 0; 
} 

// دالة قياسية لاستخراج العقدة الصغرى من الكومة
struct MinHeapNode* extractMin(struct MinHeap* minHeap) 
{ 
	if (isEmpty(minHeap)) 
		return NULL; 

	// تخزين عقدة الجذر
	struct MinHeapNode* root = minHeap->array[0]; 

	// إحلال العقدة الأخيرة محل عقدة الجذر
	struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1]; 
	minHeap->array[0] = lastNode; 

	// تحديث موقع العقدة الأخيرة
	minHeap->pos[root->v] = minHeap->size-1; 
	minHeap->pos[lastNode->v] = 0; 

	// تقليص حجم الكومة وإنشاء كومة من الجذر
	--minHeap->size; 
	minHeapify(minHeap, 0); 

	return root; 
} 

// تستخدم هذه الدالة لإنقاص قيمة المسافة للرأس المعطى
// تستخدم هذه الدالة مصفوفة المواقع الخاصة بالكومة الصغرى للحصول على الموقع الحالي للعقدة في الكومة الصغرى
void decreaseKey(struct MinHeap* minHeap, int v, int dist) 
{ 
	// الحصول على موقع الرأس المعطى في مصفوفة الكومة
	int i = minHeap->pos[v]; 

	// الحصول على العقدة وتحديث قيمة المسافة الخاصة بها
	minHeap->array[i]->dist = dist; 

	// التنقل صعودًا ما لم تحوّل الشجرة الكاملة إلى كومة
	// O(Logn) التعقيد الزمني لهذه الحلقة التكرارية يبلغ
	while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist) 
	{ 
		// تبديل هذه العقدة بالعقدة الأب
		minHeap->pos[minHeap->array[i]->v] = (i-1)/2; 
		minHeap->pos[minHeap->array[(i-1)/2]->v] = i; 
		swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]); 

		// التحرك نحو موقع العقدة الأب
		i = (i - 1) / 2; 
	} 
} 

// دالة مساعدة للتحقق من وجود الرأس المعطى في الكومة الصغرى
bool isInMinHeap(struct MinHeap *minHeap, int v) 
{ 
if (minHeap->pos[v] < minHeap->size) 
	return true; 
return false; 
} 

// دالة مساعدة لطباعة الحل
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]); 
} 

// الدالة الرئيسية التي تحسب المسافات الخاصة بالمسارات الأقصر من المصدر إلى جميع الرؤوس
// O(ELogV) يبلغ التعقيد الزمني لهذه الدالة المقدار
void dijkstra(struct Graph* graph, int src) 
{ 
	int V = graph->V;// الحصول على عدد الرؤوس في الرسم البياني
	int dist[V];	 // قيم المسافة المستخدمة لانتخاب الضلع ذي الوزن الأقل

	// E تمثل الكومة الصغرى المجموعة
	struct MinHeap* minHeap = createMinHeap(V); 

	// تهيئة الكومة الصغرى مع جميع الرؤوس، وقيمة المسافة لجميع الرؤوس
	for (int v = 0; v < V; ++v) 
	{ 
		dist[v] = INT_MAX; 
		minHeap->array[v] = newMinHeapNode(v, dist[v]); 
		minHeap->pos[v] = v; 
	} 

	// جعل قيمة المسافة للرأس المصدر هي 0 ليكون أول رأس تستخرجه الخوارزمية
	minHeap->array[src] = newMinHeapNode(src, dist[src]); 
	minHeap->pos[src] = src; 
	dist[src] = 0; 
	decreaseKey(minHeap, src, dist[src]); 

	// V يساوي حجم الكومة الصغرى في البداية
	minHeap->size = V; 

	// في الحلقة التكرارية التالية تحتوي الكومة الصغرى على جميع العقد
    // التي لم يتم الانتهاء من حساب قيمة المسافة الأصغر لها
	while (!isEmpty(minHeap)) 
	{ 
		// استخراج الرأس الذي يمتلك أصغر قيمة للمسافة
		struct MinHeapNode* minHeapNode = extractMin(minHeap); 
		int u = minHeapNode->v; // تخزين رقم الرأس المستخرج

		// التنقل عبر جميع الرؤوس المجاورة للرأس المستخرج
        // وتحديث قيم المسافة لها
		struct AdjListNode* pCrawl = graph->array[u].head; 
		while (pCrawl != NULL) 
		{ 
			int v = pCrawl->dest; 

			// إن كانت قيمة المسافة الأقصر للرأس المجاور لم تحسب بعد، وكانت المسافة
            // عبر الرأس المجاور والرأس المستخرج أقل من قيمة المسافة المحسوبة سابقًا
			if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX && 
										pCrawl->weight + dist[u] < dist[v]) 
			{ 
				dist[v] = dist[u] + pCrawl->weight; 

				// تحديث قيمة المسافة في الكومة الصغرى كذلك
				decreaseKey(minHeap, v, dist[v]); 
			} 
			pCrawl = pCrawl->next; 
		} 
	} 

	// طباعة المسارات الأقصر التي جرى حسابها
	printArr(dist, V); 
} 


// اختبار الدوال السابقة
int main() 
{ 
	// إنشاء الرسم البياني المعروض في المثال أعلاه
	int V = 9; 
	struct Graph* graph = createGraph(V); 
	addEdge(graph, 0, 1, 4); 
	addEdge(graph, 0, 7, 8); 
	addEdge(graph, 1, 2, 8); 
	addEdge(graph, 1, 7, 11); 
	addEdge(graph, 2, 3, 7); 
	addEdge(graph, 2, 8, 2); 
	addEdge(graph, 2, 5, 4); 
	addEdge(graph, 3, 4, 9); 
	addEdge(graph, 3, 5, 14); 
	addEdge(graph, 4, 5, 10); 
	addEdge(graph, 5, 6, 2); 
	addEdge(graph, 6, 7, 1); 
	addEdge(graph, 6, 8, 6); 
	addEdge(graph, 7, 8, 7); 

	dijkstra(graph, 0); 

	return 0; 
}
  • بايثون:
from collections import defaultdict 
import sys 

class Heap(): 

	def __init__(self): 
		self.array = [] 
		self.size = 0
		self.pos = [] 

	def newMinHeapNode(self, v, dist): 
		minHeapNode = [v, dist] 
		return minHeapNode 

	# دالة مساعدة للتبديل بين عقدتين
    # في الكومة الصغرى. هذه العملية مطلوبة من قبل عملية إنشاء الكومة
	def swapMinHeapNode(self,a, b): 
		t = self.array[a] 
		self.array[a] = self.array[b] 
		self.array[b] = t 

	# دالة قياسية لإنشاء الكومة عند الموقع المعطى
    # هذه الدالة تحدّث كذلك مواقع العقد
    # عند التبديل بينها
    # decreaseKey() المواقع مطلوبة من قبل الدالة
	def minHeapify(self, idx): 
		smallest = idx 
		left = 2*idx + 1
		right = 2*idx + 2

		if left < self.size and self.array[left][1] \ 
								< self.array[smallest][1]: 
			smallest = left 

		if right < self.size and self.array[right][1]\ 
								< self.array[smallest][1]: 
			smallest = right 

		# العقد التي يجب التبديل بينها في الكومة الصغرى
        # إن لم يكن الموقع هو الموقع الأصغر
		if smallest != idx: 

			# التبديل بين المواقع
			self.pos[ self.array[smallest][0] ] = idx 
			self.pos[ self.array[idx][0] ] = smallest 

			# التبديل بين العقد
			self.swapMinHeapNode(smallest, idx) 

			self.minHeapify(smallest) 

	# دالة قياسية لاستخراج العقدة الصغرى من الكومة
	def extractMin(self): 

		# الخروج من الدالة إن كانت الكومة فارغة
		if self.isEmpty() == True: 
			return

		# تخزين عقدة الجذر
		root = self.array[0] 

		# استبدال عقدة الجذر بالعقدة الأخيرة
		lastNode = self.array[self.size - 1] 
		self.array[0] = lastNode 

		# تحديث موقع العقدة الأخيرة
		self.pos[lastNode[0]] = 0
		self.pos[root[0]] = self.size - 1

		# تقليص حجم الكومة وإنشاء كومة من الجذر
		self.size -= 1
		self.minHeapify(0) 

		return root 

	def isEmpty(self): 
		return True if self.size == 0 else False

	def decreaseKey(self, v, dist): 

		# الحصول على موقع الرأس المعطى في مصفوفة الكومة

		i = self.pos[v] 

		# الحصول على العقدة وتحديث قيمة المسافة الخاصة بها
		self.array[i][1] = dist 

		# التنقل صعودًا ما لم تحوّل الشجرة الكاملة إلى كومة
        # O(Logn) يبلغ التعقيد الزمني لهذه الحلقة التكرارية المقدار
		while i > 0 and self.array[i][1] < self.array[(i - 1) / 2][1]: 

			# تبديل هذه العقدة مع العقدة الأب الخاصة بها
			self.pos[ self.array[i][0] ] = (i-1)/2
			self.pos[ self.array[(i-1)/2][0] ] = i 
			self.swapMinHeapNode(i, (i - 1)/2 ) 

			# التحرك إلى موقع العقدة الأب
			i = (i - 1) / 2; 

	# دالة مساعدة للتحق من أن الرأس المعطى موجود في الكومة الصغرى
	def isInMinHeap(self, v): 

		if self.pos[v] < self.size: 
			return True
		return False


def printArr(dist, n): 
	print "Vertex\tDistance from source"
	for i in range(n): 
		print "%d\t\t%d" % (i,dist[i]) 


class Graph(): 

	def __init__(self, V): 
		self.V = V 
		self.graph = defaultdict(list) 
	
    # تضيف الدالة ضلعًا إلى الرسم البياني غير الموجّه
	def addEdge(self, src, dest, weight): 

		# إضافة ضلع من المصدر إلى الوجهة
        # تضاف عقدة جديدة إلى قائمة المجاورة الخاصة بالمصدر.
        # تضاف العقدة في البداية
        # يمتلك العنصر الأول في العقدة الوجهة
        # ويمتلك العنصر الثاني وزن الضلع
		newNode = [dest, weight] 
		self.graph[src].insert(0, newNode) 

		# لما كان الرسم البياني غير موجّهٍ، فإنّ الضلع
        # سيضاف من الوجهة إلى المصدر كذلك
		newNode = [src, weight] 
		self.graph[dest].insert(0, newNode) 

	# الدالة الرئيسة التي تحسب المسافات
    # لأقصر المسارات من المصدر إلى جميع الرؤوس في الرسم البياني.
    # O(ELogV) يبلغ التعقيد الزمني لهذه الدالة المقدار
	def dijkstra(self, src): 

		V = self.V # الحصول على عدد الرؤوس في الرسم البياني
		dist = [] # قيم المسافة المستخدمة لانتخاب الضلع ذي الوزن الأقل 

		# E تمثل الكومة الصغرة المجموعة
		minHeap = Heap() 

		# تهيئة الكومة الصغرى مع جميع الرؤوس
        # قيمة المسافة لجميع الرؤوس
		for v in range(V): 
			dist.append(sys.maxint) 
			minHeap.array.append( minHeap.newMinHeapNode(v, dist[v]) ) 
			minHeap.pos.append(v) 

		# جعل قيمة المسافة للرأس المصدر هي 0
        # وذلك ليكون أول رأس يُستخرج من الكومة الصغرى
		minHeap.pos[src] = src 
		dist[src] = 0
		minHeap.decreaseKey(src, dist[src]) 

		# V يكون حجم الكومة الصغرى في البداية مساويًا لـ
		minHeap.size = V; 

		# في الحلقة التكرارية التالية، تحتوي الكومة الصغرى على جميع العقد
        # التي لم يتم الانتهاء من حساب قيمة المسافة الأقصر لها
		while minHeap.isEmpty() == False: 

			# استخراج الرأس مع قيمة المسافة الأقصر
			newHeapNode = minHeap.extractMin() 
			u = newHeapNode[0] 

			# التنقل عبر جميع الرؤوس المجاورة للرأس المعطى
            # وتحديث قيم المسافات الخاصة بها
			for pCrawl in self.graph[u]: 

				v = pCrawl[0] 

				# إن كانت قيمة المسافة الأقصر للرأس المجاور غير محسوبة بعد
                # وكانت المسافة من الرأس المجاور إلى الرأس الحالي أقل
                # من المسافة المحسوبة سابقًا
				if minHeap.isInMinHeap(v) and dist[u] != sys.maxint and \ 
				pCrawl[1] + dist[u] < dist[v]: 
						dist[v] = pCrawl[1] + dist[u] 

						# نحدث قيمة المسافة
						# في الكومة الصغرى كذلك
						minHeap.decreaseKey(v, dist[v]) 

		printArr(dist,V) 


# اختبار الدوال السابقة
graph = Graph(9) 
graph.addEdge(0, 1, 4) 
graph.addEdge(0, 7, 8) 
graph.addEdge(1, 2, 8) 
graph.addEdge(1, 7, 11) 
graph.addEdge(2, 3, 7) 
graph.addEdge(2, 8, 2) 
graph.addEdge(2, 5, 4) 
graph.addEdge(3, 4, 9) 
graph.addEdge(3, 5, 14) 
graph.addEdge(4, 5, 10) 
graph.addEdge(5, 6, 2) 
graph.addEdge(6, 7, 1) 
graph.addEdge(6, 8, 6) 
graph.addEdge(7, 8, 7) 
graph.dijkstra(0)

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

يبلغ التعقيد الزمني لطريقة التنفيذ الواردة أعلاه المقدار O(V^2)‎. ويمكن تخفيض هذا المقدار إلى O(E Log V)‎ إذا كان الرسم البياني ممثلًا بواسطة قائمة المجاورة وذلك بالاستعانة بالكومة الثنائية.

أسلوب الخوارزمية

هذه الخوارزمية تتبع أسلوب الخوارزميات الجشعة Greedy Algorithms.

انظر أيضًا

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

مصادر

مجلوبة من «https://wiki.hsoub.com/index.php?title=Algorithms/Dijkstra&oldid=31033»