Müsahibədə soruşduqları şey: alqoritmlərin nəzərdən keçirilməsi, 2-ci hissə

Bu məqalə mənim alqoritmlər haqqında qısa icmalımın davamıdır. Budur birinci hissəyə keçid . Əvvəllər biz müxtəlif massiv çeşidləmə alqoritmlərinə və sözdə acgöz alqoritmlərə baxırdıq . Bu gün biz onlarla əlaqəli qrafiklər və alqoritmlər haqqında danışacağıq. Qrafik proqramlaşdırmada ən çevik və çox yönlü strukturlardan biridir. G qrafiki adətən bir cüt G = (V, R) dəstindən istifadə etməklə təyin olunur , burada:

• V - təpələr dəsti;
• R təpə cütlərini birləşdirən xətlər toplusudur.

Ümumi birləşdirici xətlər adlanır kənarlar : Oxları olan xətlər - qövslər : Tipik olaraq, qrafik bəzi təpələrin kənarlar (qövslər) ilə birləşdirildiyi bir diaqramdan istifadə etməklə təmsil olunur. İstiqaməti birbaşa göstərən qövslərlə bir-birinə bağlanan qrafiklərə istiqamətləndirilmiş deyilir . Qrafiklər kənarlarla, yəni mümkün hərəkət istiqamətini göstərmədən bağlanarsa, istiqamətsiz olurlar . Bu o deməkdir ki, onlar boyunca hərəkət hər iki istiqamətdə mümkündür: həm A təpəsindən B-yə, həm də B-dən A-ya. Bağlı qrafik ən azı bir yolun hər təpədən hər hansı digər təpəyə apardığı qrafikdir (nümunədə olduğu kimi). yuxarıda). Əgər belə deyilsə, qrafik kəsilir : Həmçinin , kənarlara (qövslərə) çəkilər təyin edilə bilər - iki təpə arasındakı fiziki məsafəni (və ya iki təpə arasında keçidin nisbi vaxtını) təmsil edən nömrələr. Belə qrafiklər çəkili adlanır :

3. Yol axtarış alqoritmləri (dərinlik, genişlik)

Qrafiklərdə yerinə yetirilən əsas əməliyyatlardan biri verilmiş təpədən əldə edilə bilən bütün təpələri müəyyən etməkdir. Təsəvvür edin ki, mümkün köçürmələrlə bir şəhərdən digərinə necə getməyinizi müəyyənləşdirməyə çalışırsınız. Bəzi şəhərlərə birbaşa çatmaq olar, digərləri isə digər şəhərlərdən dolama yol tələb edir. Verilmiş təpədən yolun tapıla biləcəyi bütün təpələri tapmaq lazım ola biləcək bir çox başqa vəziyyətlər var. Beləliklə, qrafikləri keçməyin iki əsas yolu var: dərinlik-ilk keçid və genişlik-birinci keçid , biz bunları nəzərdən keçirəcəyik. Hər iki üsul bütün əlaqəli təpələr üzərində təkrarlanmağı təmin edəcəkdir. Dərinlikdən birinci və genişlikdən birinci alqoritmləri daha ətraflı nəzərdən keçirmək üçün aşağıdakı qrafiki götürün:

Dərinlik İlk keçid

Bu, ən çox yayılmış qrafik keçid üsullarından biridir. Bu dərinlik -birinci axtarış strategiyası mümkün qədər qrafikin "dərinliyinə" getməkdən və çıxılmaz nöqtəyə çatdıqdan sonra əvvəllər ziyarət edilməmiş bitişik təpələri olan ən yaxın təpəyə qayıtmaqdan ibarətdir . Bu alqoritm blokadaya çatdıqda hara qayıtmaq barədə məlumatı yığında saxlayır. Dərinliyə ilk keçid qaydaları:

1. Bitişik, əvvəllər ziyarət edilməmiş bir təpəyə baş çəkin, onu qeyd edin və yığına qoyun.
2. Bu təpəyə gedin.
3. 1-ci addımı təkrarlayın.
4. 1-ci addımı tamamlamaq mümkün deyilsə, əvvəlki təpəyə qayıdın və 1-ci qaydanı təkrarlamağa çalışın. Əgər bu mümkün deyilsə, ondan əvvəlki təpəyə qayıdın və s., biz keçidi davam etdirə biləcəyimiz təpə tapana qədər.
5. Bütün təpələr yığında olana qədər davam edin.

Gəlin bu alqoritmin kodunun Java-da necə görünə biləcəyinə nəzər salaq:

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>

Təpə belə görünür:

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

Gəlin bu alqoritmi xüsusi təpələrlə işlədək və onun düzgün işlədiyini yoxlayaq:

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

Konsol çıxışı: Qonşuluq matrisinə malik olduğumuzdan və gəzinti metodunda bir dövrə içərisində yuvalanmış bir döngədən istifadə etdiyimiz üçün zaman mürəkkəbliyi O(N²) olacaqdır .

Genişlikdə gəzin

Bu alqoritm, dərinlikdən birinci keçid kimi, qrafiki keçmək üçün ən sadə və əsas üsullardan biridir. Onun mahiyyəti ondan ibarətdir ki, bizim müəyyən cari təpəmiz var, ondan bütün bitişik, keçilməmiş təpələri növbəyə qoyuruq və onu cari etmək üçün növbəti elementi (növbədə birinci saxlanılır) seçirik... Əgər bu alqoritmi pozsaq mərhələlərdə aşağıdakı qaydaları qeyd edə bilərik:

1. Cari təpəyə bitişik olan növbəti, əvvəllər baxılmamış təpəyə baş çəkin, onu əvvəlcədən qeyd edin və növbəyə əlavə edin.
2. Qayda №1 yerinə yetirilə bilmirsə, təpəni növbədən çıxarın və onu cari təpəyə çevirin.
3. №1 və 2-ci qaydalar qeyri-mümkündürsə, keçid tamamlandı və bütün təpələr keçdi (qrafikimiz bağlıdırsa).

Qrafik sinfi, alqoritmi emal edən və daxili yığını növbə ilə əvəz edən üsul istisna olmaqla, dərinlikdən birinci axtarış alqoritmindəki oxşar siniflə demək olar ki, eynidir:

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 sinfi dərinlikdən birinci axtarış alqoritmindəki siniflə eynidir . Gəlin bu alqoritmi işə salaq:

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

Konsol çıxışı: Yenə də: bizdə bitişiklik matrisi var və bir dövrə içərisində yerləşdirilmiş bir döngədən istifadə edirik, ona görə də O(N²) yuxarıdakı alqoritmin zaman mürəkkəbliyidir.

4. Dijkstra alqoritmi

Daha əvvəl qeyd edildiyi kimi, qrafiklər istiqamətləndirilmiş və ya istiqamətsiz ola bilər . Və xatırladığınız kimi, onlar hələ də çəkilənə bilər . Çəkili, yönəldilmiş qrafiklərə tez-tez real həyatda rast gəlinir: məsələn, şəhərlərin xəritəsi, burada şəhərlər təpələrdir, onların arasındakı yollar yollardır, yollar birtərəfli hərəkətə malik ola bilər - qrafikin istiqaməti. Tutaq ki, siz yükdaşıma ilə məşğulsunuz və iki uzaq şəhər arasında ən qısa marşrutu yaratmalısınız. Bunu necə edəcəksən? Çəkili qrafikləri əhatə edən ən ümumi problemlərdən biri iki təpə arasında ən qısa yolu seçmək problemidir. Bu problemi həll etmək üçün Dijkstra alqoritmindən istifadə edirik . Dərhal qeyd etmək istərdim ki, Dijkstra alqoritmini yerinə yetirməklə biz verilmiş başlanğıcdan bütün təpələrə ən qısa yolları tapacağıq. Bu alqoritmin hansı mərhələləri var? Bu suala cavab verməyə çalışacağam. Dijkstra alqoritminin addımları:

• Mərhələ 1 : keçidin ən az xərci olacaq qovşağı axtarın. Siz ən başlanğıcda dayanırsınız və hara gedəcəyinizi düşünürsünüz: A qovşağına və ya B qovşağına. Bu qovşaqların hər birinə çatmaq nə qədər vaxt aparacaq?
• Mərhələ 2 : B -dən kənar boyunca hərəkət edərkən alqoritmdən hələ təsirlənməmiş B-nin bütün qonşularına çatmaq üçün nə qədər vaxt lazım olduğunu hesablamaq. Əgər bu yeni vaxt köhnə vaxtdan az olarsa, B kənarından keçən yol bu təpənin yeni ən qısa yolu olacaq.
• Mərhələ 3 : B təpəsini keçilmiş kimi qeyd edin.
• Addım 4 : Addım 1-ə keçin.

Bütün zirvələri keçənə qədər bu mərhələlərin dövrəsini təkrarlayacağıq. Aşağıdakı çəkili istiqamətləndirilmiş qrafiki nəzərdən keçirək: Beləliklə, yuxarıdakı alqoritmdən istifadə edərək, A-dan G-ə ən qısa yolu təyin edəcəyik:

1. A təpəsi üçün üç mümkün yol var: çəkisi 3 olan B- yə, 5 çəkisi olan C -yə və 7 çəkisi olan D -yə. Alqoritmin birinci nöqtəsinə uyğun olaraq, ən aşağı keçidi olan düyünü seçirik. xərc - yəni B -yə .
2. B üçün keçilməmiş yeganə qonşu təpə E təpəsi olduğundan , bu təpədən keçərkən yolun necə olacağını yoxlayırıq. 3( AB ) + 6( BE ) = 9.

   Beləliklə, qeyd edirik ki, AE-yə gedən ən qısa yol = 9.

3. B təpəsi ilə işimiz artıq tamamlandığından, ondan əvvəlki kənarın minimum çəkisi ilə növbəti təpənin seçilməsinə keçirik.

   A və B təpələrindən bunlar D (7), C (5), E (6) təpələri ola bilər .

   C ən kiçik kənar çəkiyə malikdir , ona görə də bu təpəyə keçirik.

4. Sonra, əvvəlki kimi, C-dən keçərkən qonşu təpələrə ən qısa yolu tapırıq:
   • AD = 5( AC ) + 3( CD ) = 8, lakin əvvəlki ən qısa yol AC = 7 olduğundan, yəni C vasitəsilə bundan kiçik olduğundan , ən qısa yolu AD = 7-ni dəyişməz qoyuruq .
   • CE = 5( AC ) + 4( CE ) = 9, bu yeni ən qısa yol əvvəlkinə bərabərdir, ona görə də onu dəyişməz qoyuruq.
5. Ən yaxın mövcud təpələrdən E və D , biz ən kiçik kənar çəkisi olan təpəni, yəni D (3) seçirik.
6. Onun qonşusuna ən qısa yolu tapırıq - F.

   AF = 7( AD ) + 3( DF ) = 10

7. Ən yaxın mövcud təpələrdən E və F , kənarın ona ən az çəkisi olan təpəni, yəni F (3) seçirik.
8. Onun qonşusuna ən qısa yolu tapırıq - G.

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

   Əslində, biz burada A - dan G- ə gedən yolu tapdıq.

   Ancaq bunun ən qısa olduğuna əmin olmaq üçün addımlarımızı E təpəsi üçün də icra etməliyik .

9. G təpəsinin yönəldilmiş yolun aparacağı qonşu təpələri olmadığı üçün bizdə yalnız E təpəsi qalıb : biz onu seçirik.
10. Qonşuya gedən ən qısa yolu tapırıq - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, bu yol əvvəlki ən qısa AG(14)-dən daha uzundur, ona görə də biz bu yolu dəyişmədən buraxırıq.

    G- dən gedən təpələr olmadığından , verilmiş təpə üçün mərhələləri işə salmağın mənası yoxdur. Buna görə də alqoritmin işini tam hesab etmək olar.

Daha əvvəl dediyim kimi, AG üçün ən qısa yolu tapmaqdan əlavə , A təpəsindən (AB, AC, AD, AE, AF) bütün təpələrə ən qısa yolları əldə etdik . Bunun Java-da necə həyata keçirilə biləcəyinə baxmaq vaxtıdır. Əvvəlcə vertex sinifinə baxaq:

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

Təpə sinfi dərinlikdən birinci və genişlikdən birinci axtarışda olan təpə sinfi ilə əslində eynidir. Ən qısa yolları göstərmək üçün bizə lazım olan məlumatları ehtiva edən yeni sinif lazımdır:

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>

Bu sinifdə biz yolun ümumi məsafəsini və ən qısa yoldan keçərkən keçəcəyi təpələri görə bilərik. İndi mən qrafikin ən qısa keçidinin baş verdiyi sinfi nəzərdən keçirmək istərdim. Beləliklə, qrafik sinfi:

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>

Əslində, bütün sehr budur =) Yaxşı, indi bu alqoritmə baxaq:

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

Və konsolda çıxış: Bu alqoritmin zaman mürəkkəbliyi O(N²) -dən başqa bir şey deyil , çünki bizdə döngələr bir dövrə içərisində yuvalanmışdır. Bu gün mənim üçün hamısı budur, diqqətinizə görə təşəkkür edirəm!