خوارزمية ديكسترا في Python & C++ (مثال)

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

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

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

سنتناول هنا خوارزمية ديكسترا. لنلقِ نظرة على الرسم البياني الموزون التالي:

رسم بياني مرجح غير موجه

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

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

أقصر الطرق

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

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

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

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

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

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

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

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

عرض توضيحي ثنائي الأبعاد لكيفية عمل خوارزمية البحث في العرض أولاً

الجوسكيتش، يظهر عرض BFS

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

لنلقِ نظرة على رسم بياني كمثال:

هنا، يجد البحث في العرض أولاً مسارًا في المستوى الثاني. يجتاز البحث في العرض أولاً الرسم البياني بترتيب المستويات. لذا، يسير على النحو التالي:

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

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

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

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

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

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

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

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

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

الخطوة 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، سيبدو الشكل كالتالي:

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

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

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

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

إليكم الشفرة الزائفة لخوارزمية ديكسترا:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- 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] && 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] && graph[U][j] &&
          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 باستخدام Pythonإليك الكود:

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] <= _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 < 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

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

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

تُستخدم خوارزمية ديكسترا في العديد من المجالات، ومن أبرزها مجال الشبكات. فيما يلي بعض الأمثلة العملية لاستخدامها:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

يمكننا تخزين الرسم البياني باستخدام "قائمة انتظار ذات أولوية". قائمة الانتظار ذات الأولوية هي بنية بيانات ثنائية. ستكون أكثر كفاءة من المصفوفة ثنائية الأبعاد. الحافة ذات التكلفة الأقل ستكون لها أولوية عالية. وبالتالي، سيكون التعقيد الزمني أقل. O(E log V). حيث E هو عدد الحواف، وV هو عدد القمم.

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

الأسئلة الشائعة