مرجع
آخر الزيارات

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

653 كلمة•0 مشاهدة•🗒️ منذ 13 يوماً
باختصار: خوارزمية ديكسترا هي خوارزمية تعنى بحل مسألة إيجاد المسار الأقصر بين عقدتين في بيان لا يحتوي على وصلات ذات أوزان سلبية. تجد هنا «{»، «marked(v) = true;» و«الاستخدامات» ضمن 9 أقسام.
المحتويات
  1. {
  2. marked(v) = true;
  3. الاستخدامات
  4. تعريف المسألة
  5. شرح الخوارزمية
  6. pq.put(dist[s], s);
  7. {
  8. int w = e.to;
  9. كود الخوارزمية
خوارزمية ديكسترا

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

{

  • boolean[] marked = new boolean[G.V]؛
  • for (int v = 0; v <G.V; v++)
  • dist[v] = Double.POSITIVE_INFINITY;
  • MinPQplus pq;
  • pq = new MinPQplus; \\Priority Queue
  • dist[s] = 0.0;

marked(v) = true;

{

for (Edge e : G.adj(v))

الاستخدامات

روابط خارجية

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

وعلى صعيد آخر، كذلك تستعمل هذه الخوارزمية في مجال شبكات الإنترنت كخوارزمية توجيه في بعض البروتوكولات مثل: بروتوكول الربط بين الأنظمة الوسيطية، كما تستعمل في بروتوكول OSPF للربط بين الأجهزة في الشبكات الداخلية.

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

تعريف المسألة

وفي هذا السياق، نريد أن نجد مساراً بسيطاً يربط بين s و-t على أن يكون وزن هذا المسار (المُعرّف على أساس مجموع أوزان الوصلات التي يتألف منها) أصغر ما يمكن.

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

الخوارزمية

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

شرح الخوارزمية

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

من جهة ثانية، أسند لكل عقدة قيمة ما تمثل المسافة: دع هذه القيمة صفراً بالنسبة للعقدة الأولية، ولانهاية بالنسبة لباقي العقد.

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

ومن ناحية أخرى، الخوارزمية تعتمد إلى حدّ كبير على انه إذا وجدنا المسار الأقصر بين v و-u لنُسمه بحيث أن k هو طول المسار ووزنه هو و- , حينئذ إذا نظرنا للمسارات الجزئية من v حتى نجد حينها أنها هي الأقصر. وهذه المُعاينة تعتمد على أنَّ الأوزان موجبة .

من جهة ثانية، عند الانتهاء من تعيين قيم كافة جيران العقدة الحالية، فإننا نعلم العقدة الحالية بأنها عقدة مزارة ونحذفها من مجموعة العقدة غير المزارة بحيث لا نقوم لاحقاً بإعادة زيارتها.

علاوةً على ذلك، اختر العقدة غير المزارة التي لديها المسافة الأصغر وعلّم هذه العقدة بأنها العقدة الحالية وعُد إلى الخطوة 3.

من جانب آخر، علّم كافة العقد بأنها غير مزارة، علّم العقدة الأولية بأنها العقدة الحالية. اصنع مجموعة من العقد التي لم تتم زيارتها بعد وادعُ هذه المجموعة مجموعة العقد غير المزارة، تتضمن هذه المجموعة بدايةً كافة العقد.

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

pq.put(dist[s], s);

  • while (!pq.isEmpty)
  • {
  • int v = pq.delMin;
  • if (marked[v]) continue;

{

  • double[] dist = new double[G.V]؛
  • Edge[] pred = new Edge[G.V]؛
  • public Dijkstra(WeightedDigraph G, int s)

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);
  • }
  • }
  • }
  • }
  • }

كود الخوارزمية

class Dijkstra

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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