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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
محاكاة بسيطة لخوارزمية دكسترا

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

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

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

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

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

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

الخوارزمية تعتمد بشكل كبير على انه اذا وجدنا المسار الاقصر بين 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);
				}
			}
		}
	}
}

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