Intervyuda nima so'rashadi: algoritmlarni ko'rib chiqish, 2-qism

Ushbu maqola mening algoritmlar bo'yicha qisqacha sharhimning davomidir. Bu erda birinchi qismga havola . Ilgari biz turli xil massivlarni saralash algoritmlarini va ochko'z algoritm deb ataladigan narsalarni ko'rib chiqdik . Bugun biz ular bilan bog'liq grafiklar va algoritmlar haqida gapiramiz. Grafik dasturlashning eng moslashuvchan va universal tuzilmalaridan biridir. Grafik G odatda juft G = (V, R) to'plamlari yordamida aniqlanadi , bu erda:

• V - cho'qqilar to'plami;
• R - juft cho'qqilarni bog'laydigan chiziqlar to'plami.

Umumiy bog'lovchi chiziqlar deyiladi qirralar : O'qlari bo'lgan chiziqlar - yoylar : Odatda, grafik diagramma yordamida ifodalanadi, unda ba'zi uchlari qirralar (yoylar) bilan bog'langan. Yo'nalishni to'g'ridan-to'g'ri ko'rsatadigan yoylar bilan bir-biriga bog'langan grafiklar deyiladi yo'naltirilgan . Agar grafiklar qirralar bilan bog'langan bo'lsa, ya'ni mumkin bo'lgan harakat yo'nalishini ko'rsatmasdan, ular yo'naltirilmagan bo'ladi . Bu shuni anglatadiki, ular bo'ylab harakatlanish har ikki yo'nalishda ham mumkin: A cho'qqisidan B gacha va B dan A cho'qqigacha. Bog'langan grafik - bu har bir cho'qqidan boshqa cho'qqiga kamida bitta yo'l olib boradigan grafik (misoldagi kabi) yuqorida). Agar bunday bo'lmasa, grafik uzilib qoladi : Bundan tashqari, qirralarga (yoylarga) og'irliklar berilishi mumkin - ikkita cho'qqi orasidagi jismoniy masofani (yoki ikkita cho'qqi orasidagi o'tishning nisbiy vaqtini) ifodalovchi raqamlar. Bunday grafiklar vaznli deb ataladi :

3. Yo'llarni qidirish algoritmlari (chuqurlik, kenglik)

Grafiklarda bajariladigan asosiy amallardan biri berilgan cho'qqidan chiqish mumkin bo'lgan barcha cho'qqilarni aniqlashdir. Tasavvur qiling-a, siz bir shahardan boshqasiga qanday o'tishni mumkin bo'lgan o'tkazmalarni aniqlashga harakat qilyapsiz. Ba'zi shaharlarga to'g'ridan-to'g'ri borish mumkin, boshqalari esa boshqa shaharlar orqali aylanma yo'lni talab qiladi. Boshqa ko'plab vaziyatlar mavjud bo'lib, ularda berilgan cho'qqidan yo'lni topish mumkin bo'lgan barcha cho'qqilarni topish kerak bo'lishi mumkin. Shunday qilib, grafiklarni kesib o'tishning ikkita asosiy usuli mavjud: chuqurlikdan birinchi o'tish va kenglikdan birinchi o'tish . Ikkala usul ham barcha ulangan cho'qqilar bo'ylab takrorlashni ta'minlaydi. Chuqurlikdan birinchi va kenglikdan birinchi algoritmlarni batafsil ko'rib chiqish uchun quyidagi grafikni oling:

Chuqurlik birinchi o'tish

Bu eng keng tarqalgan grafik o'tish usullaridan biridir. Ushbu chuqurlik - birinchi qidiruv strategiyasi iloji boricha grafikga "chuqur" kirib borishdan va boshi berk ko'chaga etib borgandan so'ng, ilgari tashrif buyurilmagan qo'shni cho'qqilarga ega bo'lgan eng yaqin cho'qqiga qaytishdan iborat . Ushbu algoritm boshi berk ko'chaga kirganida qayerga qaytish kerakligi haqidagi ma'lumotni stekda saqlaydi. Birinchi chuqurlikdan o'tish qoidalari:

1. Qo'shni, ilgari ko'rilmagan cho'qqiga tashrif buyuring, uni belgilang va stackga qo'ying.
2. Ushbu cho'qqiga o'ting.
3. 1-bosqichni takrorlang.
4. Agar 1-bosqichni bajarishning iloji bo'lmasa, oldingi cho'qqiga qayting va 1-qoidani takrorlashga urinib ko'ring. Agar buning iloji bo'lmasa, undan oldingi cho'qqiga qayting va hokazo, biz o'tishni davom ettirishimiz mumkin bo'lgan cho'qqini topmaguncha davom eting.
5. Barcha uchlari stackda bo'lguncha davom eting.

Keling, ushbu algoritm uchun kod Java-da qanday ko'rinishini ko'rib chiqaylik:

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>

Yuqori qismi quyidagicha ko'rinadi:

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

Keling, ushbu algoritmni aniq uchlari bilan ishga tushiramiz va u to'g'ri ishlayotganligini tekshiramiz:

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 chiqishi: Bizda qo'shnilik matritsasi mavjud bo'lgani uchun va yurish usulida biz halqa ichida joylashgan tsikldan foydalanamiz, vaqt murakkabligi O(N²) bo'ladi .

Kenglikda yuring

Ushbu algoritm, chuqurlikdan birinchi o'tish kabi, grafikni kesib o'tishning eng oddiy va eng asosiy usullaridan biridir. Uning mohiyati shundaki, bizda ma'lum bir joriy cho'qqi bor, biz undan barcha qo'shni, o'tmagan cho'qqilarni navbatga qo'yamiz va uni joriy qilish uchun keyingi elementni (navbatda birinchi bo'lib saqlanadi) tanlaymiz ... Agar biz ushbu algoritmni buzsak. bosqichlarida biz quyidagi qoidalarni ajratib ko'rsatishimiz mumkin:

1. Joriy cho'qqiga ulashgan keyingi, ilgari kirmagan cho'qqiga tashrif buyuring, uni oldindan belgilang va navbatga qo'shing.
2. Agar №1 qoidani bajarib bo'lmasa, cho'qqini navbatdan olib tashlang va uni joriy cho'qqiga aylantiring.
3. Agar №1 va 2-qoidalar imkonsiz bo'lsa, o'tish tugallanadi va barcha cho'qqilarni kesib o'tgan (agar bizning grafikimiz ulangan bo'lsa).

Grafik klassi chuqurlikdagi birinchi qidiruv algoritmidagi o'xshash sinf bilan deyarli bir xil, algoritmni qayta ishlaydigan va ichki stekni navbat bilan almashtiradigan usul bundan mustasno:

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 klassi chuqurlikdan birinchi qidiruv algoritmidagi sinf bilan bir xil . Keling, ushbu algoritmni harakatga keltiramiz:

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 chiqishi: Yana: bizda qo'shnilik matritsasi bor va tsikl ichida joylashgan tsikldan foydalanamiz, shuning uchun O(N²) yuqoridagi algoritmning vaqt murakkabligi.

4. Deykstra algoritmi

Yuqorida aytib o'tilganidek, grafiklar yo'naltirilgan yoki yo'naltirilmagan bo'lishi mumkin . Va siz eslaganingizdek, ular hali ham vaznga ega bo'lishi mumkin . Og'irlangan, yo'naltirilgan grafiklar ko'pincha real hayotda uchraydi: masalan, shaharlar xaritasi, bu erda shaharlar cho'qqilar, ular orasidagi yo'llar yo'llar, yo'llar bir tomonlama harakatga ega bo'lishi mumkin - grafik yo'nalishi. Aytaylik, siz yuk tashish bilan shug'ullanasiz va siz ikkita uzoq shahar o'rtasida eng qisqa yo'nalishni yaratishingiz kerak. Buni qanday qilasiz? Og'irlangan grafiklar bilan bog'liq eng keng tarqalgan muammolardan biri bu ikki cho'qqi orasidagi eng qisqa yo'lni tanlash masalasidir. Ushbu muammoni hal qilish uchun biz Dijkstra algoritmidan foydalanamiz . Darhol shuni ta'kidlashni istardimki, Dijkstra algoritmini bajarish orqali biz berilgan boshlang'ich nuqtadan barcha cho'qqilarga eng qisqa yo'llarni topamiz. Ushbu algoritm qanday bosqichlardan iborat? Men bu savolga javob berishga harakat qilaman. Dijkstra algoritmining qadamlari:

• 1-bosqich : tugunni qidiring, unga o'tish eng kam xarajat bo'ladi. Siz eng boshida turibsiz va qaerga borishni bilasiz: A tuguniga yoki B tuguniga. Ushbu tugunlarning har biriga borish uchun qancha vaqt ketadi?
• 2-bosqich : B ning chekkasi bo'ylab harakatlanayotganda, algoritm hali ta'sir qilmagan B ning barcha qo'shnilariga borish uchun qancha vaqt kerakligini hisoblash. Agar bu yangi vaqt eskisidan kamroq bo'lib chiqsa, B chetidan o'tuvchi yo'l bu cho'qqi uchun yangi eng qisqa yo'lga aylanadi.
• 3-bosqich : B cho'qqisini o'tgan deb belgilang.
• 4-qadam : 1-bosqichga o'ting.

Barcha cho'qqilarni bosib o'tmaguncha, biz ushbu bosqichlarning tsiklini takrorlaymiz. Quyidagi vaznli yo'naltirilgan grafikni ko'rib chiqamiz: Shunday qilib, yuqoridagi algoritmdan foydalanib, biz A dan G gacha bo'lgan eng qisqa yo'lni aniqlaymiz:

1. A cho'qqisi uchun uchta mumkin bo'lgan yo'llar mavjud: og'irligi 3 bo'lgan B ga, og'irligi 5 ga ega C ga va og'irligi 7 ga teng . Algoritmning birinchi nuqtasiga ko'ra, biz eng past o'tishga ega tugunni tanlaymiz. xarajat - ya'ni B ga .
2. B uchun o'tmagan yagona qo'shni cho'qqi E cho'qqisi bo'lgani uchun biz ushbu cho'qqidan o'tayotganda yo'l qanday bo'lishini tekshiramiz. 3( AB ) + 6( BE ) = 9.

   Shunday qilib, shuni ta'kidlaymizki, hozirgi eng qisqa yo'l AE = 9.

3. B cho'qqisi bilan ishimiz allaqachon tugallanganligi sababli, biz undan oldingi chekkaning minimal og'irligi bilan keyingi cho'qqini tanlashga o'tamiz.

   A va B cho'qqilardan bu D (7), C (5), E (6) uchlari bo'lishi mumkin .

   C eng kichik chekka og'irligiga ega , shuning uchun biz ushbu tepaga o'tamiz.

4. Keyinchalik, avvalgidek, biz C orqali o'tayotganda qo'shni cho'qqilarga eng qisqa yo'lni topamiz:
   • AD = 5( AC ) + 3( CD ) = 8, lekin oldingi eng qisqa yo'l AC = 7 bo'lgani uchun, ya'ni C orqali bundan kamroq bo'lgani uchun biz eng qisqa yo'l AD = 7 ni o'zgarishsiz qoldiramiz.
   • Idoralar = 5( AC ) + 4( Idoralar ) = 9, bu yangi eng qisqa yoʻl avvalgisiga teng, shuning uchun ham uni oʻzgarishsiz qoldiramiz.
5. Eng yaqin mavjud cho'qqilardan E va D , biz eng kichik chekka og'irligi bo'lgan cho'qqini tanlaymiz, ya'ni D (3).
6. Biz qo'shnisiga eng qisqa yo'lni topamiz - F.

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

7. Eng yaqin mavjud cho'qqilardan E va F , biz chekkaning eng kam og'irligi bo'lgan cho'qqini tanlaymiz, ya'ni F (3).
8. Biz uning qo'shnisiga eng qisqa yo'lni topamiz - G.

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

   Aslida, bu erda biz A dan G gacha bo'lgan yo'lni topdik.

   Ammo bu eng qisqa ekanligiga ishonch hosil qilish uchun biz E cho'qqisiga ham qadam qo'yishimiz kerak .

9. G cho'qqisiga yo'naltirilgan yo'l olib boradigan qo'shni cho'qqilari bo'lmagani uchun bizda faqat E cho'qqisi qoldi : biz uni tanlaymiz.
10. Biz qo'shniga eng qisqa yo'lni topamiz - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, bu yoʻl avvalgi eng qisqa AG(14) dan uzunroq, shuning uchun biz bu yoʻlni oʻzgarishsiz qoldiramiz.

    G dan boshlanuvchi hech qanday cho'qqi yo'qligi sababli , berilgan cho'qqi uchun bosqichlarni bajarish mantiqiy emas. Shuning uchun algoritmning ishi tugallangan deb hisoblanishi mumkin.

Yuqorida aytib o'tganimdek, AG uchun eng qisqa yo'lni topishdan tashqari , biz A cho'qqisidan (AB, AC, AD, AE, AF) barcha cho'qqilarga eng qisqa yo'llarni oldik . Xo'sh, buni Java-da qanday amalga oshirish mumkinligini ko'rib chiqish vaqti keldi. Birinchidan, vertex sinfini ko'rib chiqaylik:

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

Cho'qqi klassi aslida chuqurlikdan birinchi va kenglikdan birinchi qidiruvdagi vertex sinfiga o'xshaydi. Eng qisqa yo'llarni ko'rsatish uchun bizga kerakli ma'lumotlarni o'z ichiga olgan yangi sinf kerak:

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 sinfda biz yo'lning umumiy masofasini va eng qisqa yo'l bo'ylab o'tayotganda qoplanadigan cho'qqilarni ko'rishimiz mumkin. Va endi men grafikning eng qisqa o'tish davri sodir bo'lgan sinfni ko'rib chiqmoqchiman. Shunday qilib, grafik klassi:

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>

Aslida, bularning barchasi sehrdir =) Keling, ushbu algoritmni amalda ko'rib chiqaylik:

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

Va konsoldagi chiqish: Ushbu algoritmning vaqt murakkabligi O(N²) dan boshqa narsa emas , chunki bizda halqalar tsikl ichida joylashgan. Xo'sh, bugun men uchun hammasi shu, e'tiboringiz uchun rahmat!