Söhbetdeşlikde soraýan zatlary: algoritmlere syn, 2-nji bölüm

Bu makala algoritmler baradaky gysga synymyň dowamy. Ine, birinji bölüme baglanyşyk . Ondan öň dürli massiwleri sortlamak algoritmlerine we açgöz algoritmlere seredýärdik . Bu gün olar bilen baglanyşykly grafikler we algoritmler barada gürleşeris. Graf, programmirlemegiň iň çeýe we uniwersal gurluşlaryndan biridir. G grafigi, adatça G = (V, R) jübüt toplumyň kömegi bilen kesgitlenýär , bu ýerde:

• V dikligiň toplumy;
• R - jübüt dikligi birleşdirýän çyzyklar toplumy.

Adaty birleşdiriji çyzyklara gyralar diýilýär : Oklar bilen çyzyklar - ýaýlar : Adatça, käbir diklikler gyralar (ýaýlar) bilen birleşdirilen diagramma arkaly şekillendirilýär. Bir-birine gönüden-göni görkezýän ýaýlar bilen birleşdirilen grafalara ugrukdyrylan diýilýär . Grafalar gyralar bilen birleşdirilen bolsa, mümkin hereketiň ugruny görkezmän, ugrukdyrylmaýar . Bu, olaryň ugrunda hereketiň iki ugurda-da mümkindigini aňladýar: A nokadyndan B-e, B-den A-a çenli birikdirilen grafika , her sözlemden başga bir nokada iň bolmanda bir ýoluň gidýän grafigi (mysaldaky ýaly); ýokarda). Bu beýle bolmasa, grafik kesilýär : Şeýle hem, gyralara (ýaýlara) agramlar berlip bilner - iki dikligiň arasyndaky fiziki aralygy görkezýän sanlar (ýa-da iki dikligiň arasyndaky geçiş wagty). Şeýle grafalara agramly diýilýär :

3. searchol gözleg algoritmleri (çuňlugy, ini)

Grafalarda ýerine ýetirilýän esasy amallaryň biri, berlen sözbaşydan ýetip boljak ähli depeleri kesgitlemekdir. Mümkin bolan pul geçirimleri bilen bir şäherden beýlekisine nädip barmalydygyny kesgitlemäge synanyşýandygyňyzy göz öňüne getiriň. Käbir şäherlere göni baryp bolýar, beýlekileri beýleki şäherlerden aýlanmagy talap edýär. Berlen sözbaşydan ýol tapyp boljak ähli depeleri tapmak zerur bolup biljek başga-da köp ýagdaý bar. Şeýlelik bilen, grafikleri kesmegiň iki esasy usuly bar: göz öňünde tutjak çuňlukdan ilkinji gezelenç we giňlik-birinji gezelenç . Iki usul hem ähli birikdirilen uçlaryň üstünde gaýtalanmagy üpjün eder. Çuňlugyň we giňligiň ilkinji algoritmlerine has giňişleýin göz aýlamak üçin aşakdaky grafigi alyň:

Çuňluk Ilkinji gezelenç

Bu iň köp ýaýran grafiki gezelenç usullaryndan biridir. Bu çuňňur gözleg strategiýasy, mümkin boldugyça grafa “çuňňur” girmekden we ölmän gutarandan soň, öň görmedik ýanaşyk dikligine eýe bolan iň ýakyn nokada gaýdyp gelmekden ybaratdyr . Bu algoritm, petik gelende nirä dolanmalydygy barada maglumatlary saklaýar. Ilkinji gezelenç çuňlugynyň düzgünleri:

1. Goňşy, ozal göz öňünde tutulmadyk sözleme baryp görüň, bellik ediň we stakanyň üstünde goýuň.
2. Bu sözleme geçiň.
3. 1-nji ädimi gaýtala.
4. 1-nji ädimi tamamlamak mümkin däl bolsa, öňki sözleme gaýdyp geliň we 1-nji düzgüni gaýtalamaga synanyşyň. Bu mümkin däl bolsa, geçelgesini dowam etdirip boljak bir söz tapýançak, öňdäki sözleme we ş.m.
5. Verhli diklikler stakada bolýança dowam ediň.

Geliň, bu algoritmiň kodunyň Java-da nähili bolup biljekdigine göz aýlalyň:

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>

Dikligine meňzeýä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;
  }
}

Geliň, bu algoritmi anyk diklikler bilen işledeliň we dogry işleýändigini göreliň:

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 çykyşy: Bizde ýanaşyk matrisa bar we gezelenç usulynda bir aýlawyň içinde ýerleşdirilen aýlaw ulanýarys, wagt çylşyrymlylygy O (N²) bolar .

Giň gezelenç

Bu algoritm, çuňlukdan ilkinji gezelenç ýaly, grafany kesmegiň iň ýönekeý we iň esasy usullaryndan biridir. Onuň düýp manysy, belli bir häzirki sözlemiň bolmagydyr, ondan ähli ýanaşyk, açylmadyk diklikleri nobata goýýarys we häzirki bolmagy üçin indiki elementi (nobatda ilki saklanýar) saýlaýarys ... Bu algoritmi bozsak tapgyrlarynda aşakdaky düzgünleri belläp bileris:

1. Häzirki sözbaşy bilen ýanaşyk indiki, öň görülmedik sözleme baryp görüň, öňünden belläň we nobata goşuň.
2. 1-nji düzgün ýerine ýetirilmese, sözlemi nobatdan aýyryň we ony häzirki sözleme öwüriň.
3. # 1 we # 2 düzgünler mümkin däl bolsa, gezelenç tamamlandy we ähli diklikler kesildi (grafigimiz birikdirilen bolsa).

Grafiki synp, algoritmi gaýtadan işleýän we içki stakany nobat bilen çalyşýan usuldan başga, ilkinji gözleg algoritminden meňzeş synp bilen birmeňzeşdir:

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” synpy ilkinji gözleg algoritminden synp bilen birmeňzeşdir . Geliň, bu algoritmi herekete geçireliň:

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 çykyşy: Againene-de: ýanaşyk matrisa bar we aýlawyň içinde ýerleşdirilen aýlawy ulanýarys, şonuň üçin O (N²) ýokardaky algoritmiň wagt çylşyrymlylygydyr.

4. Dijkstranyň algoritmi

Öň bellenip geçilişi ýaly, grafikler ugrukdyrylyp ýa-da gönükdirilip bilner . Youadyňyzda bolsa, şonda-da agramy bolup biler . Agramly, gönükdirilen grafikler hakyky durmuşda köplenç tapylýar: mysal üçin, şäherleriň dikligine ýerleşýän şäherleriň kartasy, olaryň arasyndaky ýollar ýollar, ýollar bir taraplaýyn hereket edip biler - grafanyň ugry. Transportük daşamak bilen meşgullanýarsyňyz we iki uzak şäheriň arasynda iň gysga ýol döretmeli diýeliň. Muny nädip eder? Agramly grafalar bilen baglanyşykly iň köp ýaýran meseleleriň biri, iki dikligiň arasynda iň gysga ýoly saýlamak meselesidir. Bu meseläni çözmek üçin Dijkstranyň algoritmini ulanýarys . Dijkstranyň algoritmini ýerine ýetirip, berlen başlangyçdan ähli dikligine iň gysga ýollary tapjakdygymyzy derrew belläsim gelýär. Bu algoritmiň haýsy etaplary bar? Bu soraga jogap bermäge synanyşaryn. Dijkstranyň algoritminiň tapgyrlary:

• 1-nji tapgyra : iň az çykdajy boljak geçiş gözläň. Ilki başda durup, nirä barmalydygyňyzy bilýärsiňiz: A düwünine ýa-da B düwünine. Bu düwünleriň hersine näçe wagt gerek bolar?
• 2-nji tapgyra : B -den bir gyrada hereket edende algoritm täsir etmedik B goňşularyna näçe wagt gerekdigini hasaplamak. Bu täze wagt köne wagtdan az bolsa, B gyrasyndan geçýän ýol bu sözbaşy üçin iň gysga ýol bolar.
• 3-nji tapgyra : B belgisini geçen ýaly belläň.
• 4-nji ädim : 1-nji ädime geçiň.

Bu basgançaklaryň aýlawyny ähli pikler geçýänçä gaýtalarys. Aşakdaky agramly gönükdirilen grafigi gözden geçireliň: Şeýlelik bilen, ýokardaky algoritmi ulanyp, A-dan G-a çenli iň gysga ýoly kesgitläris:

1. A nokady üçin üç mümkin ýol bar: 3 agramy bilen B , 5 agramy bilen C we 7 agramy bilen D we algoritmiň birinji nokadyna görä iň pes geçiş bilen düwün saýlaýarys bahasy - ýagny B.
2. B üçin ýeke-täk öwrenilmedik goňşy sözbaşy E nokady bolany üçin , bu sözlemden geçenimizde ýoluň nähili boljakdygyny barlaýarys. 3 ( AB ) + 6 ( BE ) = 9.

   Şeýlelik bilen, AE = 9-a barýan iň gysga ýoluň bardygyny belläris.

3. B sözlemi bilen işimiz eýýäm gutaransoň, indiki gyrasy iň pes agramy bilen indiki sözlemi saýlamaga geçýäris.

   A we B depelerinden D (7), C (5), E (6) diklikler bolup biler .

   C iň kiçi gyrasy agramyna eýe , şonuň üçin bu nokada geçýäris.

4. Ondan soň, öňküsi ýaly, C-den geçenimizde goňşy depelere iň gysga ýoly tapýarys:
   • AD = 5 ( AC ) + 3 ( CD ) = 8, ýöne öňki iň gysga ýol AC = 7, ýagny bu C -den az bolany üçin, iň gysga ýoly AD = 7 üýtgewsiz goýýarys .
   • CE = 5 ( AC ) + 4 ( CE ) = 9, bu iň gysga ýol öňki ýol bilen deňdir, şonuň üçinem biz ony üýtgetmeris.
5. Iň ýakyn elýeterli E we D dikliklerinden iň kiçi gyrasy agramy bolan D (3) görnüşini saýlaýarys .
6. Goňşusyna iň gysga ýoly tapýarys - F.

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

7. Iň ýakyn elýeterli E we F dikliklerinden , gyrasynyň iň az agramy bolan Ferteksi saýlaýarys, ýagny F (3).
8. Goňşusyna iň gysga ýoly tapýarys - G.

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

   Aslynda, bu ýerde A - dan G-a çenli ýol tapdyk.

   Itöne iň gysgadygyna göz ýetirmek üçin E sözlemi üçin ädimlerimizi hem etmeli .

9. G sözbaşysynyň ugrukdyrylan ýoluň alyp barjak goňşy uçlary ýoklugy sebäpli, diňe E sözlemi galdy : ony saýlaýarys.
10. Goňşymyza iň gysga ýoly tapýarys - G.

    AG = 3 ( AB ) + 6 ( BE ) + 6 ( EG ) = 15, bu ýol öňki iň gysga AG (14) -den has uzyn, şonuň üçin bu ýoly üýtgetmän goýýarys.

    G -den öňe gidýän diklikler ýoklugy sebäpli , berlen sözbaşy üçin basgançaklary işletmegiň manysy ýok. Şonuň üçin algoritmiň işi doly hasap edilip bilner.

Öň hem aýdyşym ýaly, AG üçin iň gysga ýoly tapmakdan başga-da, A (AB, AC, AD, AE, AF) nokatlaryndan ähli dikligine iň gysga ýollary aldyk . Dogrusy, munuň Java-da nädip durmuşa geçirilip bilinjekdigine göz aýlamagyň wagty geldi. Ilki bilen, sözbaşy synpyna seredeliň:

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

Werteks synpy aslynda çuňlukdan we giňlikden gözlegden başlap, sözbaşy synpy bilen birmeňzeşdir. Iň gysga ýollary görkezmek üçin bize zerur maglumatlary öz içine alýan täze synp gerek:

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 synpda iň gysga ýoldan geçende ýoluň umumy aralygyny we depelerini görüp bileris. Indi bolsa, grafigiň iň gysga gezelençiniň bolup geçýän synpyny göz öňünde tutmak isleýärin. Şeýlelikde, grafik synpy:

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>

Aslynda bu jadylaryň hemmesi =) Indi, geliň, bu algoritmiň hereketine seredeliň:

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

Konsolda çykyş: Bu algoritmiň wagt çylşyrymlylygy O (N²) -dan başga zat däl, sebäbi bir aýlawyň içinde höwürtge bar. Bolýar, bu gün meniň üçin, ünsüňiz üçin sag boluň!