Сұхбатта не сұрайды: алгоритмдерді шолу, 2-бөлім

Бұл мақала менің алгоритмдер туралы қысқаша шолуымның жалғасы болып табылады. Міне, бірінші бөлімге сілтеме . Бұрын біз әртүрлі массивтерді сұрыптау алгоритмдерін және ашкөз алгоритм деп аталатын алгоритмдерді қарастырдық . Бүгін біз оларға қатысты графиктер мен алгоритмдер туралы айтатын боламыз. График бағдарламалаудағы ең икемді және әмбебап құрылымдардың бірі болып табылады. G графигі әдетте G = (V, R) жұбының көмегімен анықталады , мұндағы:

• V – төбелер жиыны;
• R – жұп төбелерді қосатын сызықтар жиыны.

Жалпы байланыстырушы сызықтар жиектер деп аталады : Көрсеткілері бар сызықтар - доғалар : Әдетте, график кейбір төбелер жиектермен (доғалармен) қосылған диаграмма арқылы көрсетіледі. Бағытты тікелей көрсететін доғалар арқылы бір-бірімен байланысқан графиктер бағытталған деп аталады . Егер графиктер шеттермен, яғни мүмкін болатын қозғалыс бағытын көрсетпей жалғанса, олар бағытталмаған болады . Бұл олардың бойымен қозғалыс екі бағытта да мүмкін екенін білдіреді: А төбесінен В-ға, В-дан Аға дейін. Байланысты график - бұл кем дегенде бір жол әрбір шыңнан кез келген басқа шыңға апаратын график (мысалдағыдай) жоғарыда). Олай болмаса, график ажыратылады : Сондай -ақ, жиектерге (доғаларға) салмақтар тағайындалуы мүмкін - екі төбе арасындағы физикалық қашықтықты көрсететін сандар (немесе екі шыңның арасындағы өтудің салыстырмалы уақыты). Мұндай графиктер өлшенген деп аталады :

3. Жолды іздеу алгоритмдері (тереңдік, ені)

Графиктерде орындалатын негізгі операциялардың бірі берілген төбеден жетуге болатын барлық шыңдарды анықтау болып табылады. Елестетіп көріңізші, сіз бір қаладан екінші қалаға қалай жетуге болатынын анықтауға тырысып жатырсыз. Кейбір қалаларға тікелей жетуге болады, ал басқалары басқа қалалар арқылы айналма жолды қажет етеді. Берілген шыңнан жол табуға болатын барлық шыңдарды табу қажет болуы мүмкін көптеген басқа жағдайлар бар. Сонымен, графиктерді айналдырудың екі негізгі жолы бар: тереңдік-бірінші өту және кеңдік-бірінші өту , біз оларды қарастырамыз. Екі әдіс барлық қосылған шыңдар бойынша қайталануды қамтамасыз етеді. Бірінші тереңдік және бірінші кеңдік алгоритмдерін әрі қарай қарастыру үшін келесі графикті алыңыз:

Тереңдік Бірінші өту

Бұл ең көп тараған графикті жылжыту әдістерінің бірі. Бұл тереңдік - бірінші іздеу стратегиясы графикке мүмкіндігінше «терең» өтуден және тұйыққа жеткенде бұрын бармаған көрші төбелері бар ең жақын шыңға оралудан тұрады . Бұл алгоритм тұйыққа жеткенде қай жерге оралу керектігі туралы стекке ақпаратты сақтайды. Тереңдіктен бірінші өту ережелері:

1. Көршілес, бұрын қаралмаған шыңға барыңыз, оны белгілеп, стекке қойыңыз.
2. Осы шыңға өтіңіз.
3. 1-қадамды қайталаңыз.
4. Егер 1-қадамды аяқтау мүмкін болмаса, алдыңғы шыңға оралып, 1-ережені қайталауға тырысыңыз. Егер бұл мүмкін болмаса, оның алдындағы шыңға оралыңыз және т.б., біз өтуді жалғастыра алатын шыңды тапқанша.
5. Барлық шыңдар стекте болғанша жалғастырыңыз.

Осы алгоритмнің codeы 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. Дейкстра алгоритмі

Жоғарыда айтылғандай, графиктер бағытталған немесе бағытталмаған болуы мүмкін . Естеріңізде болса, олар әлі де салмақты болуы мүмкін . Салмақты, бағытталған графиктер өмірде жиі кездеседі: мысалы, қалалар төбелері болып табылатын қалалар картасы, олардың арасындағы жолдар жолдар, жолдар бір жақты қозғалысқа ие болуы мүмкін - графиктің бағыты. Сіз жүк тасымалдаумен айналысасыз делік және сізге екі алыс қала арасындағы ең қысқа жолды жасау керек. Мұны қалай істейсіз? Салмақты графиктерге қатысты ең көп тараған есептердің бірі екі шыңның арасындағы ең қысқа жолды таңдау мәселесі болып табылады. Бұл мәселені шешу үшін біз Дийкстра алгоритмін қолданамыз . Дийкстра алгоритмін орындау арқылы біз берілген бастапқы нүктеден барлық шыңдарға ең қысқа жолдарды табатынымызды бірден атап өткім келеді. Бұл алгоритм қандай кезеңдерден тұрады? Мен бұл сұраққа жауап беруге тырысамын. Дейкстра алгоритмінің қадамдары:

• 1 кезең : өту ең аз шығын болатын түйінді іздеу. Сіз ең басында тұрып, қайда бару керектігін ойлайсыз: А түйініне немесе В түйініне. Осы түйіндердің әрқайсысына жету үшін қанша уақыт қажет?
• 2-кезең : В нүктесінен бір шет бойымен қозғалған кезде алгоритм әлі әсер етпеген В көршілеріне жету үшін қанша уақыт қажет екенін есептеу. Егер бұл жаңа уақыт бұрынғыдан аз болып шықса, В жиегі арқылы өтетін жол осы шыңның жаңа ең қысқа жолы болады.
• 3-кезең : В шыңын өткен деп белгілеңіз.
• 4-қадам : 1-қадамға өтіңіз.

Біз осы кезеңдердің циклін барлық шыңдардан өткенше қайталаймыз. Келесі салмақты бағытталған графикті қарастырайық: Сонымен, жоғарыдағы алгоритмді пайдаланып, А-дан G-ге дейінгі ең қысқа жолды анықтаймыз:

1. А шыңы үшін үш мүмкін болатын жол бар: салмағы 3 болатын В- ға, салмағы 5-ке дейінгі С-ға және салмағы 7 -ге дейін. Алгоритмнің бірінші нүктесіне сәйкес, ең төменгі өтуі бар түйінді таңдаймыз. құны – яғни, В.
2. B үшін жалғыз өтпейтін көрші төбесі Е төбесі болғандықтан , осы шың арқылы өткенде жол қандай болатынын тексереміз. 3( AB ) + 6( BE ) = 9.

   Осылайша, біз AE үшін ағымдағы ең қысқа жол = 9 екенін атап өтеміз.

3. В шыңымен жұмысымыз аяқталып қойғандықтан, оның алдындағы жиектің ең аз салмағы бар келесі төбені таңдауға көшеміз.

   А және В төбелерінен бұл D (7), С (5), Е (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. Біз оның көршісіне апаратын ең қысқа жолды анықтаймыз - Ф.

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

7. Ең жақын қол жетімді төбелерден E және F , біз оған жиегі ең аз салмағы бар шыңды таңдаймыз, яғни F (3).
8. Біз оның көршісіне апаратын ең қысқа жолды анықтаймыз - Г.

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

   Шындығында, біз А- дан G- ге дейінгі жолды таптық.

   Бірақ оның ең қысқа екеніне көз жеткізу үшін біз E шыңы үшін де қадамдарымызды орындауымыз керек .

9. G төбесінде бағытталған жол апаратын көрші төбелер болмағандықтан, бізде тек Е шыңы қалды : біз оны таңдаймыз.
10. Біз көршіге ең қысқа жолды анықтаймыз - Г.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, бұл жол алдыңғы ең қысқа AG(14) жолынан ұзын, сондықтан бұл жолды өзгеріссіз қалдырамыз.

    G нүктесінен басталатын төбелер болмағандықтан , берілген шың үшін кезеңдерді орындау мағынасы жоқ. Сондықтан алгоритм жұмысын толық деп санауға болады.

Жоғарыда айтқанымдай, AG үшін ең қысқа жолды табудан басқа , біз А шыңынан (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²) мәнінен артық емес, өйткені бізде цикл ішінде кірістірілген циклдар бар. Міне, бүгін мен үшін бәрі болды, назарларыңызға рахмет!