يرجى إعادة صياغة هذه المقالة باستخدام التنسيق العام لويكيبيديا

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

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من خوارزمية دكسترا)
اذهب إلى: تصفح، ‏ ابحث
Arwikify.svg يرجى إعادة صياغة هذه المقالة باستخدام التنسيق العام لويكيبيديا، مثل إضافة الوصلات والتقسيم إلى الفقرات وأقسام بعناوين. (يوليو 2014)


خوارزمية ديكسترا
محاكاة بسيطة لخوارزمية دكسترا
بيانات عامّة
الصنف خوارزمية بحث
بنية المعطيات بيان
التعقيد الزمني الأسوأ O(|E| + |V| \log|V|)

خوارزمية دكسترا (بالإنجليزية: Dijkstra's algorithm) هي خوارزمية تعنى بحل مشكلة إيجاد المسار الأقصر بين رأسين في [[بيان (بنية بيانات)| مع أوزان إيجابية للوصلات، المسألة مفيدة في عدة تطبيقات منها إيجاد الطريق الأقصر بين المدن في الخرائط في حين أن الأوزان قد تعني طول الشارع أو الزحمة في ذلك الشارع أو مجموعهما، واضع هذه الخوارزمية هو الهولندي ادسخر دیكسترا سنة 1959.

تعريف المسألة[عدل]

معطى مخطط G=(V,E) مع اوزان ايجابية على الأضلاع اي :  W:E\to \mathbb{R}^+ ,وكذلك مُعطى رأسين : s,t .

نريد أن نجد مسار بسيط يربط بين s و-t بحيث أن طول المسار هو الأقصر.

هذه هي المسألة بشكل عام ولكن الخوارزمية تحل مسألة أعم من هذه بحيث انَّ المسألة التي يحلها هي بإعطائنا رأس v جد كل المسارات الخفيفة بين v وباقي الرؤوس .

الخوارزمية[عدل]

سنطلق على العقدة التي نبدأ منها اسم العقدة الأولية. لتكن المسافة حتى العقدة Y هي المسافة من العقدة الأولية حتى العقدة Y. ستقوم خوارزمية دايكسترا بإسناد قيم معينة للمسافات وتحاول بعد ذلك القيام بتحسين هذه المسافات خطوة بعد خطوة.

  1. أسند لكل عقدة قيمة ما تمثل المسافة: دع هذه القيمة صفراً بالنسبة للعقدة الأولية، ولانهاية بالنسبة لباقي العقد.
  2. علّم كافة العقد بأنها غير مزارة، علّم العقدة الأولية بأنها العقدة الحالية. اصنع مجموعة من العقد التي لم تتم زيارتها بعد وادعُ هذه المجموعة مجموعة العقد غير المزارة، تتضمن هذه المجموعة بدايةً كافة العقد.
  3. قم بتحديد كافة جيران العقدة الحالية واحسب المسافات من هذه العقد إلى العقدة الحالية. قارن المسافات الجديدة مع المسافات القديمة واختر الأصغر. على سبيل المثال، لتكن العقدة الحالية A معلّمة بالمسافة 6، وليكن الضلع (الحافة) التي تصل A بالعقدة B بطول مقداره 2، وبالتالي فإن المسافة حتى العقدة B (من خلال العقدة A) ستكون 6+2=8. إذا كانت B معلمة سابقاً بمسافة أقل من 8 عندئذ لا نغير قيمة B، وإذا لم تكن كذلك فإننا نقوم بتغييرها.
  4. عند الانتهاء من تعيين قيم كافة جيران العقدة الحالية، فإننا نعلم العقدة الحالية بأنها عقدة مزارة ونحذفها من مجموعة العقدة غير المزارة بحيث لا نقوم لاحقاً بإعادة زيارتها.
  5. إذا تم تعليم العقدة الهدف بأنها عقدة مزارة (في حال البحث عن مسار بين عقدتين معطيتين) أو إذا كانت المسافة الأصغر من بين كافة العقد الموجودة في مجموعة العقد غير المزارة (في حال البحث عن جولة كاملة؛ يحدث ذلك في حال عدم وجود اتصال بين العقدة الأولية وباقي العقد غير المزارة) عندئذ يجب أن نتوقف وينتهي عمل الخوارزمية.
  6. اختر العقدة غير المزارة التي لديها المسافة الأصغر وعلّم هذه العقدة بأنها العقدة الحالية وعُد إلى الخطوة 3.

الخوارزمية تعتمد بشكل كبير على انه اذا وجدنا المسار الاقصر بين v و-u لنُسمه p=(t_0,t_1,...,t_k) بحيث ان k هو طول المسار ووزنه هو  W(p)=\sum_{i=0}^k W(t_i,t_{i+1}) و- t_0=v , حينئذ اذا نظرنا للمسارات الجزئية من v حتى t_i نجد حينها انها هي الاقصر . وهذه المُعاينة تعتمد على أنَّ الأوزان موجبة .

ما يلي هو تطبيق الخوارزمية بلغة ++C , وهذا التطبيق هو ليس الأفضل بالضرورة ولكنه نموذج لطريقة التطبيق :

class Dijkstra
{
	double[] dist = new double[G.V()];
	Edge[] pred = new Edge[G.V()];
	public Dijkstra(WeightedDigraph G, int s)
	{
		boolean[] marked = new boolean[G.V()];
		for (int v = 0; v <G.V(); v++)
			dist[v] = Double.POSITIVE_INFINITY;
		MinPQplus<Double, Integer> pq;
		pq = new MinPQplus<Double, Integer>(); \\Priority Queue 
		dist[s] = 0.0;
		pq.put(dist[s], s);
		while (!pq.isEmpty())
		{
			int v = pq.delMin();
				if (marked[v]) continue;
			marked(v) = true;
			for (Edge e : G.adj(v))
			{
				int w = e.to();
				if (dist[w]> dist[v] + e.weight())
				{
					dist[w] = dist[v] + e.weight();
					pred[w] = e;
					pq.insert(dist[w], w);
				}
			}
		}
	}
}

روابط خارجية[عدل]