خوارزمية Dijsktra: C++، مثال على كود Python

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

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

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

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

دعونا نلقي نظرة على فولوwing الرسم البياني المرجح:

رسم بياني مرجح غير موجه
رسم بياني مرجح غير موجه
  • المصطلح "المرجح" يعني نقل التكاليف من عقدة إلى أخرى. على سبيل المثال، عند الانتقال من العقدة 1 إلى العقدة 2، تكون التكلفة أو الوزن 1.
  • يسمى المسار بين العقدة 1 إلى العقدة 2 بالحافة.
  • "غير موجه" يعني أنه يمكنك نقل عقدة إلى أخرى والعودة إلى العقدة السابقة. لذلك، إذا حاولنا العثور على جميع المسارات من العقدة 1 إلى العقدة 7، فسيكون:
المسار أو المسار التكلفة
+1 2 (1+3+3) = 7
+1 2 (1+9+1) = 11
1-3-7 (7 + 1) = 8
+1 4 (6+2+5) = 13

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

أقصر الطرق

أقصر الطرق

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

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

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

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

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

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

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

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

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

مظاهرة الشبكة 2D

الجوسكيتش، شوwing مظاهرة BFS

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

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

مظاهرة الشبكة 2D

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

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

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

فيما يتعلق بـ DFS، فإنه سيجتاز المسار من 1 إلى 7 مثل المتابعةwing:

  • 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 يفعل ما يليwing:

  • يمكن لـ 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

تنفيذ خوارزمية Dijkstra في 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

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

لتنفيذ خوارزمية 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. يحتفظ جهاز التوجيه بجدول المسارات. كل جهاز التوجيه شares طاولتها مع أجهزة التوجيه المجاورة. بعد استلام الجدول المحدث، يجب عليهم حساب جميع المسارات مرة أخرى. في ذلك الوقت، يستخدم جهاز التوجيه خوارزمية Dijkstra.

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

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

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

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

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

في الرسم البياني الأيسر، هناك ثلاث قمم. سيتم تشغيل Dijkstra على الرسم البياني مثل المتابعةwing:

الخطوة 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 في حساب أقصر مسار بين عقدتين في هذا السيناريو. ونتيجة لذلك، فإن هذه الخوارزمية لديها بعض العيوب. لحل مشكلة الحافة السلبية هذه، تم استخدام خوارزمية أخرى تسمى "خوارزمية بيلمان-فورد". يمكن لهذه الخوارزمية العمل مع الحواف السلبية.

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

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

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

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

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