Алар интервьюда эмнени сурашат: алгоритмдерди карап чыгуу, 2-бөлүк

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

• V - чокулардын жыйындысы;
• R - жуп чокуларды бириктирген сызыктардын жыйындысы.

Жалпы туташтыруучу сызыктар четтери деп аталат : Жебелери бар сызыктар - жаалары : Эреже катары, график кээ бир чокулары четтери (жаалар) менен туташтырылган диаграмма аркылуу көрсөтүлөт. Багытын түз көрсөтүүчү жаалар аркылуу бири-бири менен байланышкан графиктер багытталган деп аталат . Эгерде графиктер четтери менен туташтырылса, башкача айтканда, мүмкүн болгон кыймылдын багытын көрсөтпөстөн, алар багытсыз болуп калат . Бул аларды бойлой кыймыл эки тарапта тең мүмкүн экенин билдирет: А чокусунан Вге жана Вдан Ага чейин. Байланышкан график ар бир чокудан башка чокуга жок дегенде бир жол алып баруучу график (мисалы сыяктуу) жогоруда). Эгерде андай болбосо, график ажыратылат : Ошондой эле, четтерге (жаалар) салмактар ​​ыйгарылышы мүмкүн - эки чокунун ортосундагы физикалык аралыкты (же эки чокунун ортосундагы өтүүнүн салыштырмалуу убактысын) билдирген сандар. Мындай графиктер салмактуу деп аталат :

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

Графиктерде аткарылуучу негизги операциялардын бири - берилген чокудан жетүүгө мүмкүн болгон бардык чокуларды аныктоо. Мүмкүн болгон которуулар менен бир шаардан экинчисине кантип жетүүнү аныктоого аракет кылып жатканыңызды элестетиңиз. Кээ бир шаарларга түз жетүүгө болот, ал эми башкалары башка шаарлар аркылуу айланып өтүүнү талап кылат. Берилген чокудан жол табууга мүмкүн болгон бардык чокуларды табуу зарыл болгон башка көптөгөн жагдайлар бар. Ошентип, графиктерди басып өтүүнүн эки негизги жолу бар: тереңдик-биринчи өтүү жана кеңдик-биринчи өтүү , биз аларды карап чыгабыз. Эки ыкма тең бардык туташкан чокулар боюнча кайталоону камсыз кылат. Тереңдик-биринчи жана кеңдик-биринчи алгоритмдерди андан ары карап чыгуу үчүн төмөнкү графикти алыңыз:

Тереңдик Биринчи өтүү

Бул эң кеңири таралган графикти өтүү ыкмаларынын бири. Бул тереңдик -биринчи издөө стратегиясы графикке мүмкүн болушунча "терең" кирүүдөн жана туюк чекке жеткенде, буга чейин барылбаган чектеш чокулары бар эң жакын чокуга кайтуудан турат. Бул алгоритм туюкка жеткенде каякка кайтуу керектиги жөнүндө стектеги маалыматты сактайт. Тереңдикти биринчи өтүүнүн эрежелери:

1. Кошуна турган, мурда каралбаган чокуга барыңыз, аны белгилеп, стекке коюңуз.
2. Бул чокуга барыңыз.
3. 1-кадамды кайталаңыз.
4. Эгерде 1-кадамды аяктоо мүмкүн болбосо, мурунку чокуга кайтыңыз жана 1-эрежени кайталаганга аракет кылыңыз. Эгер бул мүмкүн болбосо, анын алдындагы чокуга кайтыңыз, ж.б., биз басып өтүүнү уланта турган чоку табылганга чейин.
5. Бардык чокулар стекке болмоюнча улантыңыз.

Келгиле, бул алгоритмдин codeу Java тorнде кандай болушу мүмкүн экенин карап көрөлү:

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 алгоритмин колдонобуз . Дароо белгилеп кетким келет, Дийкстранын алгоритмин аткаруу менен биз берилген баштапкыдан бардык чокуларга эң кыска жолду табабыз. Бул алгоритм кандай этаптардан турат? Мен бул суроого жооп бергенге аракет кылам. Dijkstra алгоритминин кадамдары:

• 1-этап : түйүндү издөө, ага өтүү эң аз чыгым болот. Сиз эң башында туруп, кайда барарыңызды ойлонуп жатасыз: А түйүнүнө же В түйүнүнө. Бул түйүндөрдүн ар бирине жетүү үчүн канча убакыт талап кылынат?
• 2-этап : B чекин бойлой жылып жатканда, алгоритмге али таасир эте элек В бардык кошуналарына жетүү үчүн канча убакыт кетээрин эсептөө. Эгерде бул жаңы убакыт эски убакыттан азыраак болуп чыкса, В четинен өткөн жол бул чоку үчүн жаңы эң кыска жол болуп калат.
• 3-этап : В чокусун өттү деп белгилеңиз.
• 4-кадам : 1-кадамга өтүңүз.

Бул этаптардын циклин бардык чокулардан өткөнгө чейин кайталайбыз. Төмөнкү салмактуу багытталган графикти карап көрөлү: Ошентип, жогорудагы алгоритмди колдонуп, Адан Gге чейинки эң кыска жолду аныктайбыз:

1. А чокусу үчүн үч мүмкүн болгон жол бар: салмагы 3 болгон Вге , 5 салмагы менен Сге жана 7 салмагы менен D. Алгоритмдин биринчи пунктуна ылайык биз эң төмөнкү өткөөл түйүндү тандайбыз. наркы - башкача айтканда , Б.
2. В үчүн өтпөгөн бир гана кошуна чоку E чокусу болгондуктан , бул чокудан өткөндө жол кандай болорун текшеребиз. 3( AB ) + 6( BE ) = 9.

   Ошентип, биз AE үчүн учурдагы эң кыска жол = 9 экенин белгилейбиз.

3. В чокусу менен ишибиз бүтүп калгандыктан, анын алдындагы четинин минималдуу салмагы менен кийинки чокусун тандоого өтөбүз.

   А жана В чокуларынан бул чокулар D (7), C (5), E (6) болушу мүмкүн .

   C эң кичинекей четине ээ , ошондуктан биз бул чокуга өтөбүз.

4. Андан кийин, мурункудай эле, биз C аркылуу өткөндө коңшу чокуларга эң кыска жолду табабыз:
   • AD = 5( AC ) + 3( CD ) = 8, бирок мурунку эң кыска жол AC = 7, башкача айтканда, С аркылуу мындан аз болгондуктан , AD = 7 эң кыска жолду өзгөрүүсүз калтырабыз .
   • CE = 5( AC ) + 4( CE ) = 9, бул жаңы эң кыска жол мурункуга барабар, ошондуктан биз аны да өзгөрүүсүз калтырабыз.
5. Эң жакын жеткorктүү чокулардан, E жана D , биз эң кичине четинин салмагы менен чокусун тандайбыз, башкача айтканда, D (3).
6. Биз анын коңшусуна баруучу эң кыска жолду табабыз - Ф.

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

7. Эң жакын жеткorктүү чокулардан E жана F , биз четине эң аз салмагы бар чокуну тандайбыз, башкача айтканда, F (3).
8. Биз анын коншусуна баруучу эц кыска жолду — Г.

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

   Чынында, бул жерде биз Адан Гга чейинки жолду таптык .

   Бирок анын эң кыска экенине ынануу үчүн, E чокусуна да кадамдарыбызды аткарышыбыз керек .

9. G чокусунда багытталган жол алып бара турган кошуна чокулары жок болгондуктан, бизде бир гана E чокусу калды : биз аны тандайбыз.
10. Биз коңшуга эң кыска жолду табабыз - Г.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, бул жол мурунку эң кыска AG(14)ден узунураак, ошондуктан бул жолду өзгөрүүсүз калтырабыз.

    G чейин жеткен чокулары жок болгондуктан , берилген чоку үчүн этаптарды иштетүү мааниси жок. Демек, алгоритмдин ишин толук деп эсептөөгө болот.

Мен жогоруда айткандай, AG үчүн эң кыска жолду табуудан тышкары , биз А чокусунан (AB, AC, AD, AE, AF) бардык чокуларына эң кыска жолдорду алдык . Муну Javaда кантип ишке ашырууга болорун карап чыгууга убакыт келди. Биринчиден, vertex классын карап көрөлү:

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²) ден башка эч нерсе эмес , анткени бизде цикл ичинде уя салынган циклдер бар. Макул, бүгүн мен үчүн баары, көңүлүңүзгө рахмат!