خوارزمية ديجسكترا: C++, Python مثال رمز

ما هو أقصر طريق أو أقصر مسافة؟

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

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

هنا، نناقش حول خوارزمية ديكسترا

دعونا ننظر إلى الرسم البياني المرجح التالي:

• المصطلح "المرجح" يعني نقل التكاليف من عقدة إلى أخرى. على سبيل المثال، عند الانتقال من العقدة 1 إلى العقدة 2، تكون التكلفة أو الوزن 1.
• يسمى المسار بين العقدة 1 إلى العقدة 2 بالحافة.
• "غير موجه" يعني أنه يمكنك نقل عقدة إلى أخرى والعودة إلى العقدة السابقة. لذلك، إذا حاولنا العثور على جميع المسارات من العقدة 1 إلى العقدة 7، فسيكون:

المسار أو المسار	التكلفة
1-2-6-7+	(1+3+3) = 7
1-2-3-7+	(1+9+1) = 11
1-3-7	(7 + 1) = 8
1-4-5-7+	(6+2+5) = 13

ومن بين هذه الطرق الأربعة، يمكننا أن نرى أن الطريق الأول سيكلفنا 7 دولارات. لذا، فهو أقصر طريق من حيث التكلفة.

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

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

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

في قسم "المثال" أدناه، ستشاهد النهج خطوة بخطوة. يعمل على النحو التالي:

الخطوة 1) قم بتهيئة عقدة البداية بتكاليف 0 وبقية العقدة كتكلفة إنفينيتي.
الخطوة 2) احتفظ بمصفوفة أو قائمة لتتبع العقد التي تمت زيارتها
الخطوة 3) قم بتحديث تكلفة العقدة بأقل تكلفة. ويمكن القيام بذلك عن طريق مقارنة التكلفة الحالية بتكلفة المسار. (يتم عرض العرض التوضيحي في قسم المثال)
الخطوة 4) استمر في الخطوة 3 حتى تتم زيارة العقدة بالكامل.

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

الفرق بين ديكسترا وBFS، DFS

الفرق الرئيسي بين خوارزمية Dijkstra وBFS-DFS هو أن خوارزمية Dijkstra هي أقصر خوارزمية للعثور على المسار، بينما خوارزمية BFS,DFS هي خوارزمية للعثور على المسار. في الحالات العامة، لا تأخذ خوارزميتا BFS وDFS في الاعتبار التكلفة أثناء العثور على المسار. لذا، لا يمكن لهذه الخوارزميات ضمان أقصر مسار.

عرض شبكي ثنائي الأبعاد لكيفية عمل BFS

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

لكن دعونا نرى مثالاً بيانيًا:

هنا، يجد مسارًا في المستوى 2. يجتاز BFS الرسم البياني بترتيب المستوى. لذلك فهو يسافر مثل:

الخطوة 1) ابدأ من العقدة "1" وقم بزيارة جميع العقد المجاورة 2,3,4،XNUMX،XNUMX

الخطوة 2) حدد العقدة 2,3,4،1،XNUMX كمستوى XNUMX وقم بزيارة العقد المجاورة لها. وسوف يستمر في استكشاف جميع العقد المجاورة حتى يصل إلى العقدة الوجهة.

من حيث DFS، فإنه سوف يجتاز المسار من 1 إلى 7 مثل ما يلي:

• 1 → 2 → 3 → 7 (التكلفة الأصلية 10، تكلفة DFS 3)
• 1 → 2 → 6 → 7 (التكلفة الأصلية 7، تكلفة DFS 3)
• 1 → 3 → 7 (التكلفة الأصلية 8، تكلفة DFS 2)
• 1 → 4 → 5 → 7 (التكلفة الأصلية 13، تكلفة DFS 3)

كما نرى، يقوم DFS بحساب تكلفة مساره بعدد العمق أو عدد الحواف.

يقوم DFS بما يلي:

• يمكن لـ DFS العثور على مسار من المصدر (قمة البداية) إلى الوجهة.
• لا يمكن ضمان ما إذا كان المسار المكتشف من العقدة المصدر إلى الوجهة هو أقصر مسار أم لا.

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

مثال على خوارزمية ديكسترا

تستخدم خوارزمية ديكسترا التكلفة أو الوزن لحساب التكلفة الإجمالية للمسار.

الهدف من خوارزمية Dijkstra هو تقليل هذه التكلفة الإجمالية أو الوزن. في المثال الموضح أعلاه، نجد أفضل المسارات من العقدة 1 إلى العقدة 7، ثم نحسب جميع التكاليف.

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

لهذه العملية، يتم إعطاء الخطوات أدناه:

الخطوة 1) تهيئة تكلفة عقدة البداية إلى 0.

بقية العقدة، تعيين "المدفعية". وهذا يعني عدم وجود مسار بين قمة البداية (المصدر) والعقدة، أو أنه لم تتم زيارة المسار بعد.

الخطوة 2) عند تحديد العقدة 1، سيتم وضع علامة عليها على أنها تمت زيارتها. ثم قم بتحديث جميع الدول المجاورة للعقدة 1. 2,3,4،1،XNUMX هي العقد المجاورة للعقدة XNUMX.

أثناء تحديث التكلفة، نحتاج إلى اتباع الإجراء التالي:

يمكننا تحديث تكلفة كل عقدة باستخدام الصيغة أعلاه. على سبيل المثال، كنا في العقدة 1، وكنا بحاجة إلى تحديث تكلفة العقدة المجاورة لها 2,3,4،XNUMX،XNUMX.

بعد التحديث ستكون التكلفة أو الوزن كالتالي:

الخطوة 3) بالنسبة للعقدة "2"، الجيران هم 6 و 3. نقوم بتحديث التكلفة عند "6" من خلال مقارنة ما لا نهاية (القيمة الحالية). تكلفة العقدة 2 + تكلفة المسار من 2 إلى 6. ببساطة، العقدة "6" ستكون تكلفتها 1+3 أو 4.

العقدة 3 هي جار للعقدة 2. ومع ذلك، قمنا بحساب تكلفتها في الخطوة السابقة، والتي كانت 7. الآن، إذا كان المسار الخاص بنا هو 1-2-3، فستكون تكلفة العقدة 3 10. المسار 1-2- 3 سيكلف 10، بينما 1 إلى 3 سيكلف 7.

الخطوة 4) بالنسبة للعقدة 3، العقدة المجاورة هي 7. لذا، بمقارنة القيمة الحالية للعقدة 7 مع تكلفة المسار (7+1) أو 8، سنقوم بتحديث تكلفة العقدة 7. أي 8.

لذلك، نجد المسار من العقدة 1 إلى العقدة 7، وهو 1 → 3 → 7. التكلفة هي 8.

الخطوة 5) بالنسبة للعقدة 4، سنقوم بتحديث تكلفة العقدة المجاورة وفقًا لذلك. لذلك، ستكون تكلفة العقدة "5" محدثة بقيمة 8. بعد الخطوة 4,5،XNUMX، ستبدو كما يلي:

الآن، المسار 1-3-7 له تكلفة 8 (سابقًا). لم يتم وضع علامة على العقدة "7" كزيارة لأنه يمكننا الوصول إلى العقدة "7" من العقدة "6". المسار "1-2-6" تبلغ تكلفته 4. وبالتالي فإن المسار 1-2-6-7 ستكون تكلفته 7.

بما أن 7 < 8، فإن أقصر مسار من قمة المصدر "1" إلى قمة الوجهة "7" سيكون 1-2-6-7، والتكلفة 7. في السابق كانت 1-3-7، والتكلفة كان 8.

لذا فإن الرسم البياني النهائي سيبدو كما يلي:

الحافة المميزة بالخط الأسود هي أقصر طريق لدينا من 1 إلى 7، وسيكلفنا 7.

خوارزمية الكود الزائف Dijkstra

إليك الرمز الزائف لخوارزمية Dijkstra

Dijkstra(G, S):  
  for each vertex V in G
    distance[V] & lt; - Infinity
    previous[V] & lt; - NULL
  if V does not equal S, then, 
    (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
   U & lt; - Extract the MIN from Q
   For each unvisited adjacent V of U
   TotalDistance & lt; - distance[U] + edge_cost(U, V)
   if TotalDistance is less than distance[V], then
     distance[V] & lt; - TotalDistance
     previous[V] & lt; - u
  return distance, previous

C++ تنفيذ خوارزمية ديكسترا

لتنفيذ خوارزمية Dijkstra باستخدام C++، وإليك الكود:

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] & amp; & distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] & amp; & graph[U][j] & amp; &
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

الإخراج:

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

Python تنفيذ خوارزمية ديكسترا

لتنفيذ خوارزمية Dijkstra باستخدام الثعبان، وإليك الكود:

num_of_vertex = 7
def minimumDistance(distance, visited): 
  _min = 1e11
  min_index = 1e11
for i in range(num_of_vertex): 
  if not visited[i] and distance[i] & lt; = _min: 
   _min = distance[i]
   min_index = i
return min_index
def printParentNode(parent, i): 
  if parent[i] == -1: 
   return
  printParentNode(parent, parent[i])
  print("{} ".format(i + 1), end = "")
def dijkstra(graph, src): 
  distance = list()
  visited = list()
  parent = list()
for i in range(num_of_vertex): 
  parent.append(-1)
  distance.append(1e11)
  visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1): 
  U = minimumDistance(distance, visited)
  visited[U] = True
for j in range(num_of_vertex): 
  curr_distance = distance[U] + graph[U][j]
  if not visited[j] and graph[U][j] and curr_distance & lt;
    distance[j]: parent[j] = U
    distance[j] = curr_distance
  print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex): 
  print("{}->{}\t\t{}\t\t{} 
".format(src + 1, i + 1, distance[i], src + 1), end = "")
  printParentNode(parent, i)
print("")
graph = [
  [0, 1, 7, 6, 0, 0, 0],
  [1, 0, 9, 0, 0, 3, 0],
  [7, 9, 0, 0, 0, 0, 1],
  [6, 0, 0, 0, 2, 0, 0],
  [0, 0, 0, 2, 0, 0, 0],
  [0, 3, 0, 0, 0, 0, 3],
  [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

الإخراج:

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

يمكننا أن نرى أن الخوارزمية تحسب أقصر مسافة من العقدة المصدر.

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

يحتوي Dijkstra Algo على مجموعة كبيرة من الاستخدامات. ومن بين هذه الاستخدامات، يتم استخدامه على نطاق واسع في مجال الشبكات. إليك بعض الاستخدامات الواقعية لخوارزمية ديكسترا:

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

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

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

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

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

لا يمكن لخوارزمية Dijkstra ضمان أقصر مسار في الرسم البياني للحافة السلبية. تتبع خوارزمية ديكسترا هذه المنهجيات:

• سيتم أخذ أقصر مسار من عقدة إلى أخرى.
• بمجرد تحديد أقصر مسار بين عقدتين، لن يتم حسابه مرة أخرى.

هنا، لاحظ مثالين بحواف سلبية.

في الرسم البياني الأيسر، هناك ثلاث رؤوس. سيتم تشغيل Dijkstra على الرسم البياني على النحو التالي:

الخطوة 1) ستتم تهيئة قمة البداية "1" إلى الصفر. العقد الأخرى سيكون لها ما لا نهاية.

الخطوة 2) قم بتمييز العقدة "1" على أنها تمت زيارتها وقم بإدراجها في أقصر مسار.

الخطوة 3) تم ضبط مسافة العقدة المصدر 1 إلى العقدتين "2" و"3" على ما لا نهاية، حيث لم يتم بعد حساب أقصر مسار. لذلك، أي مسار سيكون أقل تكلفة من اللانهاية سيتم إضافته إلى أقصر مسار (النهج الجشع).

الخطوة 4) تحديث المسافة من قمة المصدر أو عقدة المصدر "1" إلى "2". الوزن الحالي سيكون 5 (5

الخطوة 5) الآن إذا تحققنا من أقصر المسافات من العقدة "1"، نجد أن 5 هي أقصر مسافة للحافة 1-> 2. لذا، سيتم وضع علامة على العقدة "2" على أنها تمت زيارتها.

وبالمثل، سيتم أيضًا وضع علامة على العقدة "3" على أنها تمت زيارتها حيث أن أقصر مسافة هي 3.

ومع ذلك، إذا لاحظنا أن هناك مسار 1-3-2 سيكلف 2 فقط. لكن Dijkstra يوضح أنه من العقدة "1" إلى العقدة "2"، فإن أقصر مسافة هي 5. لذا، فشل Dijkstra في حساب أقصر مسافة المسافة بشكل صحيح. سبب حدوث ذلك هو أن Dijkstra هي خوارزمية جشعة. لذلك، بمجرد وضع علامة على العقدة بأنها تمت زيارتها، لن تتم إعادة النظر فيها، على الرغم من أنه قد يكون هناك مسار أقصر متاحًا. تحدث هذه المشكلة فقط عندما تكون الحواف ذات تكاليف سالبة أو حواف ذات وزن سالب

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

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

استخدم التنفيذ أعلاه حلقتين "for". تعمل هاتان الحلقتان لعدد الرؤوس. لذا، فإن تعقيد الوقت هو يا(ف²). هنا المصطلح "0" يعني تدوينًا يعطي افتراضًا لخوارزمية Dijkstra.

يمكننا تخزين الرسم البياني باستخدام "قائمة انتظار الأولوية". قائمة الانتظار ذات الأولوية هي بنية بيانات كومة الذاكرة المؤقتة الثنائية. سيكون أكثر كفاءة من مصفوفة ثنائية الأبعاد. الحافة التي سيكون لها الحد الأدنى من التكلفة ستكون لها أولوية عالية.

ثم ستكون تعقيدات الوقت O (تسجيل E (V)). حيث E هو عدد الحواف، وV هو عدد القمم.

تعقيد الفضاء هو يا(ف²)، لأننا نستخدم مصفوفة الجوار (مجموعة 2Dيمكن تحسين تعقيد المساحة باستخدام قائمة مجاورة أو بنية بيانات قائمة انتظار.