Họ hỏi gì khi phỏng vấn: xem xét các thuật toán, phần 2

Bài viết này là sự tiếp nối bài đánh giá ngắn gọn của tôi về các thuật toán. Đây là liên kết đến phần đầu tiên . Trước đây, chúng ta đã xem xét các thuật toán sắp xếp mảng khác nhau và cái gọi là thuật toán tham lam . Hôm nay chúng ta sẽ nói về đồ thị và thuật toán liên quan đến chúng. Biểu đồ là một trong những cấu trúc linh hoạt và linh hoạt nhất trong lập trình. Đồ thị G thường được xác định bằng cách sử dụng một cặp tập hợp G = (V, R) , trong đó:

• V là tập các đỉnh;
• R là tập hợp các đường nối các cặp đỉnh.

Các đường kết nối thông thường được gọi là các cạnh : Các đường có mũi tên - cung : Thông thường, một đồ thị được biểu diễn bằng sơ đồ trong đó một số đỉnh được nối với nhau bằng các cạnh (cung). Các đồ thị nối với nhau bằng các cung chỉ hướng trực tiếp gọi là đồ thị có hướng . Nếu các đồ thị được kết nối bởi các cạnh, nghĩa là không chỉ ra hướng chuyển động có thể, chúng sẽ trở thành vô hướng . Điều này có nghĩa là có thể di chuyển dọc theo chúng theo cả hai hướng: cả từ đỉnh A đến B và từ B đến A. Đồ thị liên thông là một đồ thị trong đó có ít nhất một đường dẫn từ mỗi đỉnh đến bất kỳ đỉnh nào khác (như trong ví dụ bên trên ). Nếu không đúng như vậy, đồ thị sẽ bị ngắt kết nối : Ngoài ra, các cạnh (cung) có thể được gán trọng số - các số biểu thị khoảng cách vật lý giữa hai đỉnh (hoặc thời gian chuyển tiếp tương đối giữa hai đỉnh). Các đồ thị như vậy được gọi là có trọng số :

3. Thuật toán tìm kiếm đường dẫn (độ sâu, chiều rộng)

Một trong những thao tác cơ bản được thực hiện trên đồ thị là xác định tất cả các đỉnh có thể tiếp cận được từ một đỉnh đã cho. Hãy tưởng tượng rằng bạn đang cố gắng xác định cách đi từ thành phố này sang thành phố khác bằng các phương tiện di chuyển có thể. Một số thành phố có thể đến thẳng được, trong khi những thành phố khác yêu cầu đi đường vòng qua các thành phố khác. Có nhiều tình huống khác trong đó có thể cần phải tìm tất cả các đỉnh mà đường đi có thể tìm được từ một đỉnh cho trước. Vì vậy, có hai cách chính để duyệt đồ thị: duyệt theo chiều sâu và duyệt theo chiều rộng mà chúng ta sẽ xem xét. Cả hai phương pháp sẽ đảm bảo lặp lại trên tất cả các đỉnh được kết nối. Để xem xét thêm về các thuật toán theo chiều sâu và chiều rộng , hãy xem biểu đồ sau:

Độ sâu truyền tải đầu tiên

Đây là một trong những phương pháp duyệt đồ thị phổ biến nhất. Chiến lược tìm kiếm theo chiều sâu này bao gồm việc đi “sâu” vào biểu đồ càng xa càng tốt và khi đi đến ngõ cụt, quay trở lại đỉnh gần nhất có các đỉnh liền kề chưa được ghé thăm trước đó. Thuật toán này lưu trữ thông tin trên ngăn xếp về nơi cần quay lại khi gặp bế tắc. Quy tắc duyệt theo chiều sâu lần đầu:

1. Thăm một đỉnh liền kề, chưa được thăm trước đó, đánh dấu nó và đặt nó vào ngăn xếp.
2. Đi đến đỉnh này.
3. Lặp lại bước 1.
4. Nếu không thể hoàn thành bước 1, hãy quay lại đỉnh trước đó và thử lặp lại quy tắc 1. Nếu điều này là không thể, hãy quay lại đỉnh trước nó, v.v., cho đến khi chúng ta tìm thấy một đỉnh mà từ đó chúng ta có thể tiếp tục duyệt.
5. Tiếp tục cho đến khi tất cả các đỉnh đều nằm trong ngăn xếp.

Chúng ta hãy xem mã cho thuật toán này trông như thế nào trong 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>

Phần trên trông giống như:

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

Hãy chạy thuật toán này với các đỉnh cụ thể và xem nó có hoạt động chính xác không:

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

Đầu ra của bảng điều khiển: Vì chúng ta có ma trận kề và trong phương thức đi bộ, chúng ta sử dụng một vòng lặp được lồng trong một vòng lặp, nên độ phức tạp về thời gian sẽ là O(N²) .

Đi theo chiều rộng

Thuật toán này, giống như thuật toán duyệt theo chiều sâu, là một trong những phương pháp đơn giản và cơ bản nhất để duyệt đồ thị. Bản chất của nó là chúng ta có một đỉnh hiện tại nhất định, từ đó chúng ta đặt tất cả các đỉnh liền kề, không được giao nhau vào một hàng đợi và chọn phần tử tiếp theo (được lưu đầu tiên trong hàng đợi) để làm cho nó hiện tại... Nếu chúng ta chia thuật toán này thành giai đoạn, chúng ta có thể nêu bật các quy tắc sau:

1. Truy cập đỉnh tiếp theo, chưa được thăm trước đó liền kề với đỉnh hiện tại, đánh dấu trước và thêm nó vào hàng đợi.
2. Nếu quy tắc số 1 không thể được thực hiện, hãy xóa đỉnh khỏi hàng đợi và đặt nó làm đỉnh hiện tại.
3. Nếu quy tắc số 1 và số 2 là không thể thực hiện được thì quá trình duyệt hoàn thành và tất cả các đỉnh đã được duyệt (nếu đồ thị của chúng ta được kết nối).

Lớp biểu đồ gần giống với lớp tương tự của thuật toán tìm kiếm theo chiều sâu, ngoại trừ phương thức xử lý thuật toán và thay thế ngăn xếp bên trong bằng hàng đợi:

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>

Lớp Vertex giống hệt với lớp của thuật toán tìm kiếm theo chiều sâu . Hãy áp dụng thuật toán này vào hoạt động:

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

Đầu ra của bảng điều khiển: Một lần nữa: chúng ta có ma trận kề và sử dụng một vòng lặp lồng trong một vòng lặp, vì vậy O(N²) là độ phức tạp về thời gian của thuật toán trên.

4. Thuật toán Dijkstra

Như đã đề cập trước đó, đồ thị có thể có hướng hoặc vô hướng . Và như bạn nhớ, chúng vẫn có thể được cân . Đồ thị có trọng số, có hướng thường thấy trong đời thực: ví dụ: bản đồ thành phố, trong đó các thành phố là các đỉnh, đường đi giữa chúng là đường, đường có thể có giao thông một chiều - hướng của đồ thị. Giả sử bạn đang tham gia vận chuyển hàng hóa và bạn cần tạo tuyến đường ngắn nhất giữa hai thành phố xa xôi. Làm thế nào bạn sẽ làm điều này? Một trong những bài toán thường gặp nhất liên quan đến đồ thị có trọng số là bài toán chọn đường đi ngắn nhất giữa hai đỉnh. Để giải quyết vấn đề này chúng ta sử dụng thuật toán Dijkstra . Tôi muốn lưu ý ngay rằng bằng cách thực hiện thuật toán Dijkstra, chúng ta sẽ tìm ra đường đi ngắn nhất tới tất cả các đỉnh từ một đỉnh đầu tiên cho trước. Thuật toán này có những giai đoạn nào? Tôi sẽ cố gắng trả lời câu hỏi này. Các giai đoạn của thuật toán Dijkstra:

• Giai đoạn 1 : tìm kiếm nút, quá trình chuyển đổi sang nút đó sẽ có chi phí thấp nhất. Bạn đang đứng ngay từ đầu và tự hỏi phải đi đâu: đến nút A hay nút B. Sẽ mất bao lâu để đến được từng nút này?
• Giai đoạn 2 : tính toán cần bao nhiêu thời gian để đến được tất cả các lân cận của B mà chưa bị ảnh hưởng bởi thuật toán khi di chuyển dọc theo một cạnh từ B. Nếu thời gian mới này nhỏ hơn thời gian cũ thì đường đi qua cạnh B sẽ trở thành đường đi ngắn nhất mới cho đỉnh này.
• Giai đoạn 3 : đánh dấu đỉnh B là đã vượt qua.
• Bước 4 : Chuyển sang Bước 1.

Chúng ta sẽ lặp lại chu kỳ của các giai đoạn này cho đến khi vượt qua tất cả các đỉnh. Hãy xem xét đồ thị có hướng có trọng số sau: Vì vậy, bằng cách sử dụng thuật toán trên, chúng ta sẽ xác định đường đi ngắn nhất từ ​​A đến G:

1. Đối với đỉnh A, có ba đường đi có thể: đến B có trọng số là 3, đến C có trọng số là 5 và đến D có trọng số là 7. Theo điểm đầu tiên của thuật toán, chúng ta chọn nút có độ chuyển tiếp thấp nhất chi phí - nghĩa là đối với B.
2. Vì đỉnh lân cận duy nhất không bị cắt của B là đỉnh E nên chúng ta kiểm tra xem đường đi sẽ như thế nào khi đi qua đỉnh này. 3( AB ) + 6( BE ) = 9.

   Vì vậy, chúng ta lưu ý rằng đường đi ngắn nhất hiện tại tới AE = 9.

3. Vì công việc của chúng ta với đỉnh B đã hoàn thành nên chúng ta chuyển sang chọn đỉnh tiếp theo có trọng số tối thiểu của cạnh trước nó.

   Từ các đỉnh A và B có thể là các đỉnh D (7), C (5), E (6).

   C có trọng số cạnh nhỏ nhất nên chúng ta chuyển sang đỉnh này.

4. Tiếp theo, như trước, chúng ta tìm đường đi ngắn nhất tới các đỉnh lân cận khi đi qua C:
   • AD = 5( AC ) + 3( CD ) = 8, nhưng vì đường đi ngắn nhất trước đó AC = 7, tức là nhỏ hơn đường đi ngắn nhất trước đó đi qua C nên chúng ta giữ nguyên đường đi ngắn nhất AD = 7.
   • CE = 5( AC ) + 4( CE ) = 9, đường đi ngắn nhất mới này bằng đường đi ngắn nhất trước đó nên chúng ta cũng giữ nguyên.
5. Từ các đỉnh có sẵn gần nhất, E và D , chúng ta chọn đỉnh có trọng số cạnh nhỏ nhất, đó là D (3).
6. Chúng tôi tìm ra con đường ngắn nhất đến người hàng xóm của nó - F.

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

7. Từ các đỉnh có sẵn gần nhất E và F , chúng ta chọn đỉnh có trọng số cạnh nhỏ nhất đối với nó, đó là F (3).
8. Chúng tôi tìm ra con đường ngắn nhất đến người hàng xóm của nó - G.

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

   Thực ra ở đây chúng ta đã tìm được đường đi từ A đến G.

   Nhưng để đảm bảo rằng nó là ngắn nhất, chúng ta cũng phải chạy các bước cho đỉnh E .

9. Vì đỉnh G không có các đỉnh lân cận mà đường đi có hướng sẽ dẫn tới nên chúng ta chỉ còn lại đỉnh E : chúng ta chọn nó.
10. Chúng tôi tìm ra con đường ngắn nhất đến hàng xóm - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, đường đi này dài hơn đường đi ngắn nhất AG(14 trước đó), nên chúng ta giữ nguyên đường đi này.

    Vì không có đỉnh nào dẫn từ G nên việc chạy các giai đoạn cho một đỉnh nhất định là vô nghĩa. Vì vậy, công việc của thuật toán có thể được coi là hoàn thành.

Như tôi đã nói trước đó, ngoài việc tìm đường đi ngắn nhất cho AG , chúng ta còn tìm được đường đi ngắn nhất tới tất cả các đỉnh từ đỉnh A (AB, AC, AD, AE, AF) . Chà, đã đến lúc xem xét cách triển khai điều này trong Java. Đầu tiên, chúng ta hãy nhìn vào lớp đỉnh:

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

Lớp đỉnh thực sự giống với lớp đỉnh từ tìm kiếm theo chiều sâu và chiều rộng. Để hiển thị các đường đi ngắn nhất, chúng ta cần một lớp mới chứa dữ liệu chúng ta cần:

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>

Trong lớp này, chúng ta có thể thấy tổng khoảng cách của đường đi và các đỉnh sẽ bị che khi đi dọc theo đường đi ngắn nhất. Và bây giờ tôi muốn xem xét lớp trong đó trên thực tế, việc truyền đồ thị ngắn nhất xảy ra. Vì vậy, lớp đồ thị:

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>

Trên thực tế, đó là tất cả những điều kỳ diệu =) Bây giờ, chúng ta hãy xem thuật toán này hoạt động như thế nào:

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

Và đầu ra trong bảng điều khiển: Độ phức tạp về thời gian của thuật toán này không lớn hơn O(N2) vì chúng ta có các vòng lặp được lồng trong một vòng lặp. Vâng, đó là tất cả đối với tôi ngày hôm nay, cảm ơn sự quan tâm của bạn!