Ano ang itatanong nila sa isang panayam: pagsusuri ng mga algorithm, bahagi 2

Ang artikulong ito ay isang pagpapatuloy ng aking maikling pagsusuri sa mga algorithm. Narito ang link sa unang bahagi . Noong nakaraan, tiningnan namin ang iba't ibang algorithm ng pag-uuri ng array at ang tinatawag na greedy algorithm . Ngayon ay pag-uusapan natin ang tungkol sa mga graph at algorithm na nauugnay sa kanila. Ang graph ay isa sa mga pinaka-flexible at versatile na istruktura sa programming. Ang isang graph G ay karaniwang tinutukoy gamit ang isang pares ng mga set G = (V, R) , kung saan:

• Ang V ay ang hanay ng mga vertex;
• Ang R ay ang hanay ng mga linyang nag-uugnay sa mga pares ng vertices.

Ang mga karaniwang linya ng pagkonekta ay tinatawag na mga gilid : Mga linyang may mga arrow - mga arko : Karaniwan, ang isang graph ay kinakatawan gamit ang isang diagram kung saan ang ilang mga vertice ay konektado sa pamamagitan ng mga gilid (mga arko). Ang mga graph na konektado sa isa't isa sa pamamagitan ng mga arko na direktang nagpapahiwatig ng direksyon ay tinatawag na nakadirekta . Kung ang mga graph ay konektado sa pamamagitan ng mga gilid, iyon ay, nang hindi nagpapahiwatig ng direksyon ng posibleng paggalaw, sila ay nagiging hindi nakadirekta . Nangangahulugan ito na ang paggalaw sa kahabaan ng mga ito ay posible sa parehong direksyon: parehong mula sa vertex A hanggang B, at mula sa B hanggang A. Ang konektadong graph ay isang graph kung saan ang hindi bababa sa isang path ay humahantong mula sa bawat vertex patungo sa anumang iba pang vertex (tulad ng sa halimbawa sa itaas). Kung hindi ito ang kaso, ang graph ay madidiskonekta : Gayundin, ang mga gilid (mga arko) ay maaaring magtalaga ng mga timbang - mga numerong kumakatawan sa pisikal na distansya sa pagitan ng dalawang vertice (o ang kaugnay na oras ng paglipat sa pagitan ng dalawang vertices). Ang ganitong mga graph ay tinatawag na weighted :

3. Mga algorithm sa paghahanap ng landas (lalim, lapad)

Ang isa sa mga pangunahing operasyon na ginagawa sa mga graph ay upang matukoy ang lahat ng mga vertex na maaabot mula sa isang naibigay na vertex. Isipin na sinusubukan mong matukoy kung paano pumunta mula sa isang lungsod patungo sa isa pa na may mga posibleng paglipat. Ang ilang mga lungsod ay maaaring direktang maabot, habang ang iba ay nangangailangan ng isang detour sa iba pang mga lungsod. Mayroong maraming iba pang mga sitwasyon kung saan maaaring kailanganin upang mahanap ang lahat ng mga vertex kung saan ang isang landas ay matatagpuan mula sa isang naibigay na vertex. Kaya, mayroong dalawang pangunahing paraan upang tumawid sa mga graph: depth-first traversal at breadth-first traversal , na aming isasaalang-alang. Ang parehong mga pamamaraan ay titiyakin na umuulit sa lahat ng konektadong mga vertex. Para sa karagdagang pagsasaalang-alang ng depth-first at breadth-first algorithm , kunin ang sumusunod na graph:

Lalim Unang Paglalakbay

Ito ay isa sa mga pinakakaraniwang paraan ng pag-travers ng graph. Ang depth -first na diskarte sa paghahanap na ito ay binubuo ng "malalim" sa graph hangga't maaari, at kapag naabot ang isang dead end, bumalik sa pinakamalapit na vertex na may mga katabing vertex na hindi pa nabisita. Ang algorithm na ito ay nag-iimbak ng impormasyon sa stack tungkol sa kung saan babalik kapag naabot ang isang deadlock. Mga panuntunan para sa depth first traversal:

1. Bisitahin ang isang katabing, dati nang hindi nabisitang vertex, markahan ito at ilagay ito sa stack.
2. Pumunta sa tuktok na ito.
3. Ulitin ang hakbang 1.
4. Kung imposibleng kumpletuhin ang hakbang 1, bumalik sa nakaraang vertex at subukang ulitin ang panuntunan 1. Kung imposible ito, bumalik sa vertex bago nito, at iba pa, hanggang sa makakita tayo ng vertex kung saan maaari nating ipagpatuloy ang traversal.
5. Magpatuloy hanggang ang lahat ng vertices ay nasa stack.

Tingnan natin kung ano ang maaaring hitsura ng code para sa algorithm na ito sa 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>

Ang vertex ay mukhang:

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

Patakbuhin natin ang algorithm na ito gamit ang mga partikular na vertice at tingnan kung gumagana ito nang tama:

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

Output ng console: Dahil mayroon kaming adjacency matrix at sa paraan ng paglalakad ay gumagamit kami ng loop na naka-nest sa loob ng loop, ang pagiging kumplikado ng oras ay O(N²) .

Maglakad sa lapad

Ang algorithm na ito, tulad ng depth-first traversal, ay isa sa pinakasimple at pinakapangunahing pamamaraan para sa pagtawid sa isang graph. Ang kakanyahan nito ay mayroon tayong isang tiyak na kasalukuyang vertex, kung saan inilalagay natin ang lahat ng katabi, hindi nababagong mga vertex sa isang pila at piliin ang susunod na elemento (na unang nakaimbak sa pila) upang gawin itong kasalukuyang... Kung sisirain natin ang algorithm na ito sa mga yugto, maaari naming i-highlight ang mga sumusunod na patakaran:

1. Bisitahin ang susunod, dati nang hindi nabisitang vertex na katabi ng kasalukuyang vertex, markahan ito nang maaga at idagdag ito sa pila.
2. Kung hindi matutupad ang panuntunan #1, alisin ang vertex sa queue at gawin itong kasalukuyang vertex.
3. Kung ang mga panuntunan #1 at #2 ay imposible, ang traversal ay nakumpleto at ang lahat ng mga vertex ay nalampasan (kung ang aming graph ay konektado).

Ang graph class ay halos magkapareho sa katulad na klase mula sa depth-first search algorithm, maliban sa paraan na nagpoproseso ng algorithm at pinapalitan ang panloob na stack ng isang queue:

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>

Ang klase ng Vertex ay kapareho ng klase mula sa depth-first search algorithm . Gawin natin ang algorithm na ito sa pagkilos:

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

Output ng console: Muli: mayroon kaming adjacency matrix at gumamit ng loop na naka-nest sa loob ng loop, kaya ang O(N²) ay ang pagiging kumplikado ng oras ng algorithm sa itaas.

4. Algoritmo ni Dijkstra

Tulad ng nabanggit kanina, ang mga graph ay maaaring idirekta o hindi idirekta . At gaya ng naaalala mo, maaari pa rin silang timbangin . Ang mga matimbang, nakadirekta na mga graph ay madalas na matatagpuan sa totoong buhay: halimbawa, isang mapa ng mga lungsod, kung saan ang mga lungsod ay vertices, ang mga landas sa pagitan ng mga ito ay mga kalsada, ang mga kalsada ay maaaring magkaroon ng one-way na trapiko - ang direksyon ng graph. Sabihin nating nakikibahagi ka sa transportasyon ng kargamento at kailangan mong lumikha ng pinakamaikling ruta sa pagitan ng dalawang malalayong lungsod. Paano mo ito gagawin? Ang isa sa mga pinakakaraniwang problema na kinasasangkutan ng mga weighted graph ay ang problema sa pagpili ng pinakamaikling landas sa pagitan ng dalawang vertices. Upang malutas ang problemang ito ginagamit namin ang algorithm ng Dijkstra . Nais kong agad na tandaan na sa pamamagitan ng pagpapatupad ng algorithm ng Dijkstra malalaman natin ang pinakamaikling landas sa lahat ng mga vertices mula sa isang naibigay na paunang isa. Anong mga yugto mayroon ang algorithm na ito? Susubukan kong sagutin ang tanong na ito. Mga yugto ng algorithm ng Dijkstra:

• Stage 1 : hanapin ang node, ang paglipat kung saan ang pinakamababang gastos. Nakatayo ka sa pinakasimula at nag-iisip kung saan pupunta: sa node A o sa node B. Gaano katagal bago makarating sa bawat isa sa mga node na ito?
• Stage 2 : pagkalkula kung gaano katagal bago makarating sa lahat ng kapitbahay ng B na hindi pa naaapektuhan ng algorithm kapag lumilipat sa gilid mula sa B. Kung ang bagong oras na ito ay lumabas na mas mababa kaysa sa luma, ang landas sa gilid B ay magiging bagong pinakamaikling landas para sa vertex na ito.
• Stage 3 : markahan ang vertex B bilang naipasa.
• Hakbang 4 : Pumunta sa Hakbang 1.

Uulitin natin ang ikot ng mga yugtong ito hanggang sa maipasa ang lahat ng mga taluktok. Isaalang-alang natin ang sumusunod na weighted directed graph: Kaya, gamit ang algorithm sa itaas, tutukuyin natin ang pinakamaikling landas mula A hanggang G:

1. Para sa vertex A mayroong tatlong posibleng mga landas: sa B na may timbang na 3, hanggang C na may timbang na 5 at sa D na may timbang na 7. Ayon sa unang punto ng algorithm, pipiliin namin ang node na may pinakamababang paglipat gastos - iyon ay, sa B.
2. Dahil ang tanging hindi natawid na kalapit na vertex para sa B ay ang vertex E , tinitingnan namin kung ano ang magiging landas kapag dumadaan sa vertex na ito. 3( AB ) + 6( BE ) = 9.

   Kaya, tandaan namin na ang kasalukuyang pinakamaikling landas sa AE = 9.

3. Dahil nakumpleto na ang aming trabaho sa vertex B , nagpapatuloy kami sa pagpili ng susunod na vertex na may pinakamababang bigat ng gilid bago nito.

   Mula sa mga vertice A at B ang mga ito ay maaaring mga vertex D (7), C (5), E (6).

   Ang C ay may pinakamaliit na gilid na timbang , kaya nagpapatuloy kami sa tuktok na ito.

4. Susunod, tulad ng dati, nalaman natin ang pinakamaikling landas patungo sa mga kalapit na vertice kapag dumadaan sa C:
   • AD = 5( AC ) + 3( CD ) = 8, ngunit dahil ang nakaraang pinakamaikling landas AC = 7, iyon ay, mas mababa sa isang ito hanggang C , iniiwan namin ang pinakamaikling landas AD = 7 na hindi nagbabago.
   • CE = 5( AC ) + 4( CE ) = 9, ang bagong pinakamaikling landas na ito ay katumbas ng nauna kaya hinahayaan din namin itong hindi nagbabago.
5. Mula sa pinakamalapit na available na vertices, E at D , pipiliin namin ang vertex na may pinakamaliit na bigat ng gilid, iyon ay, D (3).
6. Nalaman namin ang pinakamaikling landas patungo sa kapitbahay nito - F.

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

7. Mula sa pinakamalapit na available na vertex E at F , pipiliin namin ang vertex na may pinakamababang bigat ng gilid dito, iyon ay, F (3).
8. Nalaman natin ang pinakamaikling landas patungo sa kapitbahay nito - G.

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

   Sa totoo lang, nahanap namin ang landas mula A hanggang G.

   Ngunit upang matiyak na ito ang pinakamaikling, kailangan din nating patakbuhin ang ating mga hakbang para sa vertex E .

9. Dahil walang kalapit na vertex ang vertex G kung saan hahantong ang isang nakadirekta na landas, vertex E na lang ang natitira namin : pipiliin namin ito.
10. Nalaman namin ang pinakamaikling landas patungo sa kapitbahay - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, ang landas na ito ay mas mahaba kaysa sa nakaraang pinakamaikling AG(14), kaya iniiwan namin ang landas na ito na hindi nagbabago.

    Dahil walang mga vertex na humahantong mula sa G , walang saysay na magpatakbo ng mga yugto para sa isang partikular na vertex. Samakatuwid, ang gawain ng algorithm ay maaaring ituring na kumpleto.

Gaya ng sinabi ko kanina, bilang karagdagan sa paghahanap ng pinakamaikling landas para sa AG , nakuha namin ang pinakamaikling landas sa lahat ng vertex mula sa vertex A (AB, AC, AD, AE, AF) . Well, oras na upang tingnan kung paano ito maipapatupad sa Java. Una, tingnan natin ang klase ng 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;
   }
}

Ang vertex class ay talagang magkapareho sa vertex class mula sa depth-first at breadth-first na paghahanap. Upang magpakita ng pinakamaikling landas, kailangan namin ng bagong klase na maglalaman ng data na kailangan namin:

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>

Sa klase na ito makikita natin ang kabuuang distansya ng landas at ang mga vertice na matatakpan kapag dumaan sa pinakamaikling landas. At ngayon gusto kong isaalang-alang ang klase kung saan, sa katunayan, ang pinakamaikling pag-traversal ng graph ay nangyayari. Kaya, ang klase ng graph:

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>

Sa totoo lang, iyon lang ang magic =) Well, ngayon, tingnan natin ang algorithm na ito sa aksyon:

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

At ang output sa console: Ang pagiging kumplikado ng oras ng algorithm na ito ay hindi hihigit sa O(N²) dahil mayroon kaming mga loop na nakapugad sa loob ng isang loop. Well, iyon lang para sa akin ngayon, salamat sa iyong pansin!