ما الذي يسألونه في المقابلة: مراجعة الخوارزميات، الجزء 2

هذه المقالة هي استمرار لمراجعتي القصيرة حول الخوارزميات. هنا هو الرابط للجزء الأول . في السابق، نظرنا إلى خوارزميات فرز المصفوفات المختلفة وما يسمى بالخوارزمية الجشعة . اليوم سنتحدث عن الرسوم البيانية والخوارزميات المتعلقة بها. يعد الرسم البياني واحدًا من أكثر الهياكل مرونة وتنوعًا في البرمجة. عادةً ما يتم تحديد الرسم البياني G باستخدام زوج من المجموعات G = (V, R) حيث:

• الخامس - مجموعة من القمم.
• R هي مجموعة الخطوط التي تربط بين أزواج القمم.

تسمى خطوط التوصيل الشائعة بالحواف : الخطوط ذات الأسهم - الأقواس : عادة، يتم تمثيل الرسم البياني باستخدام رسم تخطيطي حيث يتم توصيل بعض القمم بواسطة الحواف (الأقواس). الرسوم البيانية المتصلة ببعضها البعض بواسطة أقواس تشير مباشرة إلى الاتجاه تسمى موجهة . إذا كانت الرسوم البيانية متصلة بحواف، أي دون الإشارة إلى اتجاه الحركة المحتملة، فإنها تصبح غير موجهة . وهذا يعني أن الحركة على طولها ممكنة في كلا الاتجاهين: من الرأس A إلى B، ومن B إلى A. الرسم البياني المتصل هو رسم بياني يؤدي فيه مسار واحد على الأقل من كل قمة إلى أي قمة أخرى (كما في المثال فوق ). إذا لم يكن الأمر كذلك، يصبح الرسم البياني غير متصل : أيضًا، يمكن تعيين أوزان للحواف (الأقواس) - أرقام تمثل المسافة المادية بين رأسين (أو الوقت النسبي للانتقال بين رأسين). تسمى هذه الرسوم البيانية مرجحة :

3. خوارزميات البحث عن المسار (العمق، العرض)

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

العمق الأول اجتياز

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

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

دعونا نلقي نظرة على الشكل الذي قد يبدو عليه رمز هذه الخوارزمية في Java:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Stack<integer> stack;

  public Graph() { // инициализация внутрених полей
     vertexArray = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {
           adjMat[j][k] = 0;
        }
     }
     stack = new Stack<>();
  }

  public void addVertex(char lab) {
     vertexArray[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexArray[v].getLabel());
  }

  public void dfs() { // обход в глубину
     vertexArray[0].setWasVisited(true); // берётся первая вершина
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
        if (v == -1) { // если непройденных смежных вершин нету
           stack.pop(); // элемент извлекается из стека
        }
        else {
           vertexArray[v].setWasVisited(true);
           displayVertex(v);
           stack.push(v); // элемент попадает на вершину стека
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexArray[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

تبدو قمة الرأس كما يلي:

public class Vertex {
  private char label;  // метка А например
  public boolean wasVisited;

  public Vertex(final char label) {
     this.label = label;
     wasVisited = false;
  }

  public char getLabel() {
     return this.label;
  }

  public boolean isWasVisited() {
     return this.wasVisited;
  }

  public void setWasVisited(final boolean wasVisited) {
     this.wasVisited = wasVisited;
  }
}

لنقم بتشغيل هذه الخوارزمية برؤوس محددة ونرى ما إذا كانت تعمل بشكل صحيح:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.dfs();
  }
}

إخراج وحدة التحكم: نظرًا لأن لدينا مصفوفة مجاورة وفي طريقة المشي نستخدم حلقة متداخلة داخل حلقة، فإن التعقيد الزمني سيكون O(N²) .

المشي في العرض

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

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

تتطابق فئة الرسم البياني تقريبًا مع الفئة المشابهة من خوارزمية بحث العمق الأول، باستثناء الطريقة التي تعالج الخوارزمية وتستبدل المكدس الداخلي بقائمة انتظار:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Queue<integer> queue;

  public Graph() {
     vertexList = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {  // заполнение матрицы смежности нулями
           adjMat[j][k] = 0;
        }
     }
     queue = new PriorityQueue<>();
  }

  public void addVertex(char lab) {
     vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexList[v].getLabel());
  }

  public void bfc() { // обход в глубину
     vertexList[0].setWasVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

     while (!queue.isEmpty()) {
        int v = queue.remove();

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
           vertexList[v2].wasVisited =true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexList[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

فئة Vertex مماثلة للفئة الموجودة في خوارزمية بحث العمق الأول . دعونا نضع هذه الخوارزمية موضع التنفيذ:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.bfc();
  }
}

إخراج وحدة التحكم: مرة أخرى: لدينا مصفوفة مجاورة ونستخدم حلقة متداخلة داخل حلقة، لذا فإن O(N²) هو التعقيد الزمني للخوارزمية المذكورة أعلاه.

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

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

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

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

1. بالنسبة للقمة A هناك ثلاثة مسارات محتملة: إلى B بوزن 3، إلى C بوزن 5 وإلى D بوزن 7. وفقًا للنقطة الأولى من الخوارزمية، نختار العقدة ذات الانتقال الأدنى التكلفة - أي إلى B.
2. نظرًا لأن الرأس المجاور الوحيد الذي لم يتم اجتيازه لـ B هو الرأس E ، فإننا نتحقق من المسار الذي سيكون عليه عند المرور عبر هذا الرأس. 3( أ ب ) + 6 ( ب ) = 9.

   وهكذا نلاحظ أن أقصر طريق حالي إلى AE = 9.

3. وبما أن عملنا مع الرأس B قد اكتمل بالفعل، فإننا ننتقل إلى اختيار الرأس التالي مع الحد الأدنى من وزن الحافة التي قبله.

   من القمم A و B يمكن أن تكون هذه القمم D (7)، C (5)، E (6).

   C لديه أصغر وزن للحافة ، لذلك ننتقل إلى هذه القمة.

4. بعد ذلك، كما كان من قبل، نكتشف أقصر طريق إلى القمم المجاورة عند المرور عبر C:
   • AD = 5( AC ) + 3( CD ) = 8، ولكن بما أن المسار الأقصر السابق AC = 7، أي أقل من هذا المسار حتى C ، فإننا نترك أقصر مسار AD = 7 دون تغيير.
   • CE = 5( AC ) + 4( CE ) = 9، هذا المسار الأقصر الجديد يساوي المسار السابق لذا نتركه دون تغيير أيضًا.
5. من أقرب القمم المتاحة، E و D ، نختار الرأس ذو أصغر وزن للحافة، أي D (3).
6. نكتشف أقصر طريق إلى جارتها - F.

   التركيز البؤري التلقائي = 7( م ) + 3( مدافع ) = 10

7. من أقرب القمم المتاحة E و F ، نختار الرأس الذي له أقل وزن للحافة، أي F (3).
8. نكتشف أقصر طريق إلى جارتها - G.

   AG = 7( AD ) + 3 ( DF ) + 4 ( FG ) = 14

   في الواقع، لقد وجدنا هنا المسار من A إلى G.

   ولكن للتأكد من أنه الأقصر، يجب علينا تشغيل خطواتنا للقمة E أيضًا .

9. نظرًا لأن الرأس G لا يحتوي على رؤوس مجاورة يمكن أن يؤدي إليها المسار الموجه، فلن يتبقى لدينا سوى الرأس E : نختاره.
10. نكتشف أقصر طريق إلى الجار - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15، هذا المسار أطول من أقصر AG(14) السابق، لذلك نترك هذا المسار دون تغيير.

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

كما قلت سابقًا، بالإضافة إلى العثور على أقصر مسار لـ AG ، حصلنا على أقصر المسارات لجميع القمم من الرأس A (AB، AC، AD، AE، AF) . حسنًا، حان الوقت للنظر في كيفية تنفيذ ذلك في Java. أولاً، دعونا نلقي نظرة على فئة قمة الرأس:

public class Vertex {
   private char label;
   private boolean isInTree;

   public Vertex(char label) {
       this.label = label;
       this.isInTree = false;
   }

   public char getLabel() {
       return label;
   }

   public void setLabel(char label) {
       this.label = label;
   }

   public boolean isInTree() {
       return isInTree;
   }

   public void setInTree(boolean inTree) {
       isInTree = inTree;
   }
}

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

public class Path { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
   private int distance; // текущая дистанция от начальной вершины
   private List<integer> parentVertices; // текущий родитель вершины

   public Path(int distance) {
       this.distance = distance;
       this.parentVertices = new ArrayList<>();
   }

   public int getDistance() {
       return distance;
   }

   public void setDistance(int distance) {
       this.distance = distance;
   }

   public List<integer> getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List<integer> parentVertices) {
       this.parentVertices = parentVertices;
   }
}
</integer></integer></integer>

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

public class Graph {
   private final int MAX_VERTS = 10;// максимальное количество вершин
   private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
   private Vertex vertexList[]; // список вершин
   private int relationMatrix[][]; // матрица связей вершин
   private int countOfVertices; // текущее количество вершин
   private int countOfVertexInTree; // количество рассмотренных вершин в дереве
   private List<path> shortestPaths; // список данных кратчайших путей
   private int currentVertex; // текущая вершина
   private int startToCurrent; //расстояние до currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // матрица смежности
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       countOfVertices = 0;
       countOfVertexInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
           for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
               relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
               shortestPaths = new ArrayList<>();// задается пустым
           }
       }
   }

   public void addVertex(char lab) {// задание новых вершин
       vertexList[countOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
   }

   public void path() { // выбор кратчайшего пути
       //  задание данных для стартовой вершины
       int startTree = 0; // стартуем с вершины 0
       vertexList[startTree].setInTree(true); // включение в состав дерева первого element
       countOfVertexInTree = 1;

       // заполнение коротких путей для вершин смежных с стартовой
       for (int i = 0; i < countOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
           shortestPaths.add(path);
       }
       // пока все вершины не окажутся в дереве
       while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
           int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
           int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве

           if (minDist == INFINITY) {
               System.out.println("В графе пристувствуют недостижимые вершины");
               break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
           } else {
               currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
               startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
           }

           vertexList[currentVertex].setInTree(true);  //включение текущей вершины в дерево
           countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
           updateShortestPaths(); // обновление списка кратчайших путей
       }

       displayPaths(); // выводим в консоль результаты
   }

   public void clean() { // очиска дерева
       countOfVertexInTree = 0;
       for (int i = 0; i < countOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // за точку старта взята "бесконечная" длина
       int indexMin = 0;
       for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
               minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
               indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
           }
       }
       return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // стартовая вершина пропускается
       while (vertexIndex < countOfVertices) { // перебор столбцов

           if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
               vertexIndex++;
               continue;
           }
           // вычисление расстояния для одного element sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего element vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
           if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
               List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
               newParents.add(currentVertex);// задаём в него и currentVertex How предыдущий
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // метод для вывода кратчайших путей на экран
       for (int i = 0; i < countOfVertices; i++) {
           System.out.print(vertexList[i].getLabel() + " = ");
           if (shortestPaths.get(i).getDistance() == INFINITY) {
               System.out.println("0");
           } else {
               String result = shortestPaths.get(i).getDistance() + " (";
               List<integer> parents = shortestPaths.get(i).getParentVertices();
               for (int j = 0; j < parents.size(); j++) {
                   result += vertexList[parents.get(j)].getLabel() + " -> ";
               }
               System.out.println(result + vertexList[i].getLabel() + ")");
           }
       }
   }
}
</integer></integer></path>

في الواقع، هذا هو كل السحر =) حسنًا، الآن، دعونا نلقي نظرة على هذه الخوارزمية أثناء العمل:

public class Solution {

   public static void main(String[] args) {
       Graph graph = new Graph();
       graph.addVertex('A');
       graph.addVertex('B');
       graph.addVertex('C');
       graph.addVertex('D');
       graph.addVertex('E');
       graph.addVertex('F');
       graph.addVertex('G');

       graph.addEdge(0, 1, 3);
       graph.addEdge(0, 2, 5);
       graph.addEdge(0, 3, 7);
       graph.addEdge(1, 4, 6);
       graph.addEdge(2, 4, 4);
       graph.addEdge(2, 3, 3);
       graph.addEdge(3, 5, 3);
       graph.addEdge(4, 6, 6);
       graph.addEdge(5, 6, 4);

       System.out.println("Элементы имеют кратчайшие пути из точки A: ");
       graph.path();
       graph.clean();
   }
}

والإخراج في وحدة التحكم: التعقيد الزمني لهذه الخوارزمية ليس أكثر من O(N²) حيث أن لدينا حلقات متداخلة داخل حلقة. حسنًا، هذا كل شيء بالنسبة لي اليوم، شكرًا لاهتمامكم!