Was sie in einem Interview fragen: Überprüfung von Algorithmen, Teil 2

Dieser Artikel ist eine Fortsetzung meiner kurzen Rezension zu Algorithmen. Hier der Link zum ersten Teil . Zuvor haben wir uns verschiedene Array-Sortieralgorithmen und den sogenannten Greedy-Algorithmus angesehen . Heute werden wir über Diagramme und damit verbundene Algorithmen sprechen. Ein Graph ist eine der flexibelsten und vielseitigsten Strukturen in der Programmierung. Ein Graph G wird normalerweise durch ein Mengenpaar G = (V, R) spezifiziert , wobei:

• V ist die Menge der Eckpunkte;
• R ist die Menge der Linien, die Scheitelpunktpaare verbinden.

Übliche Verbindungslinien werden Kanten genannt : Linien mit Pfeilen – Bögen : Typischerweise wird ein Graph mithilfe eines Diagramms dargestellt, in dem einige Eckpunkte durch Kanten (Bögen) verbunden sind. Graphen, die durch Bögen miteinander verbunden sind, die direkt die Richtung angeben, werden als gerichtet bezeichnet . Wenn die Graphen durch Kanten verbunden sind, also ohne Angabe der Richtung einer möglichen Bewegung, werden sie ungerichtet . Dies bedeutet, dass eine Bewegung entlang ihnen in beide Richtungen möglich ist: sowohl von Scheitelpunkt A nach B als auch von B nach A. Ein verbundener Graph ist ein Graph, in dem mindestens ein Pfad von jedem Scheitelpunkt zu jedem anderen Scheitelpunkt führt (wie im Beispiel). über ). Ist dies nicht der Fall, wird der Graph getrennt : Außerdem können Kanten (Bögen) Gewichtungen zugewiesen werden – Zahlen, die den physischen Abstand zwischen zwei Scheitelpunkten (oder die relative Zeit des Übergangs zwischen zwei Scheitelpunkten) darstellen. Solche Diagramme werden gewichtet genannt :

3. Pfadsuchalgorithmen (Tiefe, Breite)

Eine der grundlegenden Operationen, die an Diagrammen ausgeführt werden, besteht darin, alle Scheitelpunkte zu bestimmen, die von einem bestimmten Scheitelpunkt aus erreichbar sind. Stellen Sie sich vor, Sie versuchen herauszufinden, wie Sie mit möglichen Transfers von einer Stadt in eine andere gelangen. Manche Städte sind direkt erreichbar, andere erfordern einen Umweg über andere Städte. Es gibt viele andere Situationen, in denen Sie möglicherweise alle Scheitelpunkte finden müssen, zu denen Sie von einem bestimmten Scheitelpunkt aus einen Pfad finden können. Es gibt also im Wesentlichen zwei Möglichkeiten, Graphen zu durchlaufen: die Tiefendurchquerung und die Breitendurchquerung , die wir betrachten werden. Beide Methoden stellen sicher, dass alle verbundenen Scheitelpunkte durchlaufen werden. Zur weiteren Betrachtung der Tiefen- und Breitenalgorithmen sehen Sie sich das folgende Diagramm an:

Tiefendurchquerung

Dies ist eine der gebräuchlichsten Methoden zum Durchlaufen von Graphen. Diese Tiefensuchstrategie besteht darin, so weit wie möglich „tief“ in den Graphen vorzudringen und beim Erreichen einer Sackgasse zum nächstgelegenen Scheitelpunkt zurückzukehren, der benachbarte Scheitelpunkte hat, die zuvor noch nicht besucht wurden . Dieser Algorithmus speichert auf dem Stapel Informationen darüber, wohin er zurückkehren soll, wenn ein Deadlock erreicht wird. Regeln für die Tiefendurchquerung:

1. Besuchen Sie einen benachbarten, bisher nicht besuchten Scheitelpunkt, markieren Sie ihn und legen Sie ihn auf den Stapel.
2. Gehen Sie zu diesem Gipfel.
3. Wiederholen Sie Schritt 1.
4. Wenn es nicht möglich ist, Schritt 1 abzuschließen, kehren Sie zum vorherigen Scheitelpunkt zurück und versuchen Sie, Regel 1 zu wiederholen. Wenn dies nicht möglich ist, kehren Sie zum Scheitelpunkt davor zurück und so weiter, bis wir einen Scheitelpunkt finden, von dem aus wir die Durchquerung fortsetzen können.
5. Fahren Sie fort, bis alle Scheitelpunkte auf dem Stapel liegen.

Schauen wir uns an, wie der Code für diesen Algorithmus in Java aussehen könnte:

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>

Die Oberseite sieht aus wie:

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

Lassen Sie uns diesen Algorithmus mit bestimmten Scheitelpunkten ausführen und prüfen, ob er richtig funktioniert:

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

Konsolenausgabe: Da wir eine Adjazenzmatrix haben und in der Walk-Methode eine in einer Schleife verschachtelte Schleife verwenden, beträgt die Zeitkomplexität O(N²) .

Breites Kriechen

Dieser Algorithmus ist wie die Tiefendurchquerung eine der einfachsten und grundlegendsten Methoden zum Durchlaufen eines Diagramms. Sein Wesen besteht darin, dass wir einen bestimmten aktuellen Scheitelpunkt haben, von dem aus wir alle benachbarten, nicht durchlaufenen Scheitelpunkte in eine Warteschlange stellen und das nächste Element auswählen (das zuerst in der Warteschlange gespeichert wird), um es zum aktuellen zu machen ... Wenn wir diesen Algorithmus aufteilen Phasen können wir die folgenden Regeln hervorheben:

1. Besuchen Sie den nächsten, bisher nicht besuchten Scheitelpunkt neben dem aktuellen Scheitelpunkt, markieren Sie ihn im Voraus und fügen Sie ihn der Warteschlange hinzu.
2. Wenn Regel Nr. 1 nicht erfüllt werden kann, entfernen Sie den Scheitelpunkt aus der Warteschlange und machen Sie ihn zum aktuellen Scheitelpunkt.
3. Wenn die Regeln Nr. 1 und Nr. 2 unmöglich sind, ist die Durchquerung abgeschlossen und alle Eckpunkte wurden durchlaufen (sofern unser Graph verbunden ist).

Die Graph-Klasse ist fast identisch mit der ähnlichen Klasse aus dem Tiefensuchalgorithmus, mit Ausnahme der Methode, die den Algorithmus verarbeitet und den internen Stapel durch eine Warteschlange ersetzt:

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>

Die Vertex- Klasse ist identisch mit der Klasse aus dem Tiefensuchalgorithmus . Lassen Sie uns diesen Algorithmus in die Tat umsetzen:

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

Konsolenausgabe: Nochmals: Wir haben eine Adjazenzmatrix und verwenden eine Schleife, die in einer Schleife verschachtelt ist, also ist O(N²) die zeitliche Komplexität des obigen Algorithmus.

4. Dijkstras Algorithmus

Wie bereits erwähnt, können Graphen gerichtet oder ungerichtet sein . Und wie Sie sich erinnern, können sie immer noch gewichtet werden . Gewichtete, gerichtete Diagramme findet man oft im wirklichen Leben: zum Beispiel eine Karte von Städten, bei der die Städte Eckpunkte sind, die Wege zwischen ihnen Straßen sind, Straßen können Einbahnverkehr haben – die Richtung des Diagramms. Nehmen wir an, Sie sind im Gütertransport tätig und müssen die kürzeste Route zwischen zwei weit entfernten Städten schaffen. Wie machen Sie das? Eines der häufigsten Probleme bei gewichteten Graphen ist die Wahl des kürzesten Weges zwischen zwei Eckpunkten. Um dieses Problem zu lösen, verwenden wir den Dijkstra-Algorithmus . Ich möchte sofort darauf hinweisen, dass wir durch die Ausführung des Dijkstra-Algorithmus die kürzesten Wege zu allen Scheitelpunkten von einem gegebenen Anfangspunkt aus herausfinden werden. Welche Stufen hat dieser Algorithmus? Ich werde versuchen, diese Frage zu beantworten. Phasen des Dijkstra-Algorithmus:

• Stufe 1 : Suche nach dem Knoten, zu dem der Übergang am wenigsten kostet. Sie stehen ganz am Anfang und fragen sich, wohin Sie gehen sollen: zu Knoten A oder zu Knoten B. Wie lange wird es dauern, bis jeder dieser Knoten erreicht ist?
• Stufe 2 : Berechnen, wie lange es dauert, alle Nachbarn von B zu erreichen, die noch nicht vom Algorithmus betroffen sind , wenn man sich entlang einer Kante von B bewegt. Wenn sich herausstellt, dass diese neue Zeit kürzer als die alte ist, wird der Pfad durch Kante B zum neuen kürzesten Pfad für diesen Scheitelpunkt.
• Stufe 3 : Markieren Sie Scheitelpunkt B als bestanden.
• Schritt 4 : Gehen Sie zu Schritt 1.

Wir werden den Zyklus dieser Etappen wiederholen, bis alle Gipfel erreicht sind. Betrachten wir den folgenden gewichteten gerichteten Graphen: Mit dem obigen Algorithmus ermitteln wir also den kürzesten Weg von A nach G:

1. Für Scheitelpunkt A gibt es drei mögliche Pfade: zu B mit einem Gewicht von 3, zu C mit einem Gewicht von 5 und zu D mit einem Gewicht von 7. Gemäß dem ersten Punkt des Algorithmus wählen wir den Knoten mit dem niedrigsten Übergang aus Kosten - also für B.
2. Da der einzige nicht durchquerte benachbarte Scheitelpunkt für B der Scheitelpunkt E ist , prüfen wir, wie der Pfad aussehen wird, wenn er durch diesen Scheitelpunkt verläuft. 3( AB ) + 6( BE ) = 9.

   Daher stellen wir fest, dass der derzeit kürzeste Weg zu AE = 9 ist.

3. Da unsere Arbeit mit Scheitelpunkt B bereits abgeschlossen ist, fahren wir mit der Auswahl des nächsten Scheitelpunkts mit dem minimalen Gewicht der Kante davor fort.

   Von den Eckpunkten A und B können dies die Eckpunkte D (7), C (5), E (6) sein.

   C hat das kleinste Kantengewicht , also gehen wir zu diesem Scheitelpunkt über.

4. Als nächstes ermitteln wir wie zuvor den kürzesten Weg zu benachbarten Eckpunkten beim Durchgang durch C:
   • AD = 5( AC ) + 3( CD ) = 8, aber da der bisherige kürzeste Weg AC = 7 ist, also kleiner als dieser durch C , lassen wir den kürzesten Weg AD = 7 unverändert.
   • CE = 5( AC ) + 4( CE ) = 9, dieser neue kürzeste Weg ist gleich dem vorherigen, also lassen wir ihn auch unverändert.
5. Aus den nächstgelegenen verfügbaren Scheitelpunkten E und D wählen wir den Scheitelpunkt mit dem kleinsten Kantengewicht aus, d. h. D (3).
6. Wir finden den kürzesten Weg zu seinem Nachbarn heraus – F.

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

7. Aus den nächstgelegenen verfügbaren Scheitelpunkten E und F wählen wir den Scheitelpunkt mit dem geringsten Gewicht der Kante aus, also F (3).
8. Wir finden den kürzesten Weg zu seinem Nachbarn heraus – G.

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

   Eigentlich haben wir hier den Weg von A nach G gefunden.

   Aber um sicherzustellen, dass es das kürzeste ist, müssen wir unsere Schritte auch für den Scheitelpunkt E ausführen .

9. Da der Scheitelpunkt G keine benachbarten Scheitelpunkte hat, zu denen ein gerichteter Pfad führen würde, bleibt uns nur noch der Scheitelpunkt E übrig : Wir wählen ihn aus.
10. Wir finden den kürzesten Weg zum Nachbarn heraus – G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, dieser Pfad ist länger als der vorherige kürzeste AG(14), daher lassen wir diesen Pfad unverändert.

    Da es keine Scheitelpunkte gibt, die von G ausgehen , macht es keinen Sinn, Stufen für einen bestimmten Scheitelpunkt auszuführen. Daher kann die Arbeit des Algorithmus als abgeschlossen betrachtet werden.

Wie ich bereits sagte, haben wir nicht nur den kürzesten Weg für AG gefunden , sondern auch die kürzesten Wege zu allen Scheitelpunkten vom Scheitelpunkt A (AB, AC, AD, AE, AF) erhalten . Nun ist es an der Zeit, einen Blick darauf zu werfen, wie dies in Java implementiert werden kann. Schauen wir uns zunächst die Vertex-Klasse an:

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

Die Vertex-Klasse ist tatsächlich identisch mit der Vertex-Klasse aus der Tiefensuche und der Breitensuche. Um kürzeste Wege anzuzeigen, benötigen wir eine neue Klasse, die die benötigten Daten enthält:

public class Path { // ein Objekt данного класса содержащий расстояние и предыдущие и пройденные вершины
   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>

In dieser Klasse können wir die Gesamtstrecke des Pfades und die Eckpunkte sehen, die beim Durchlaufen des kürzesten Pfades zurückgelegt werden. Und jetzt möchte ich die Klasse betrachten, in der tatsächlich die kürzeste Durchquerung des Graphen stattfindet. Also die Graphklasse:

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 Wie предыдущий
               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>

Eigentlich ist das die ganze Magie =) Schauen wir uns nun diesen Algorithmus in Aktion an:

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

Und die Ausgabe in der Konsole: Die zeitliche Komplexität dieses Algorithmus beträgt nichts anderes als O(N²) , da wir Schleifen haben, die in einer Schleife verschachtelt sind. Nun, das ist alles für mich heute, vielen Dank für Ihre Aufmerksamkeit!