Dieser Artikel stellt den auf Java basierenden Dijkstra-Algorithmus in Form von Beispielen vor. Ich glaube, dass er den Lesern beim Studium und Erlernen von Datenstrukturdomänenalgorithmen hilfreich sein wird.
Dijkstra schlug einen Algorithmus vor, um den kürzesten Weg zu jedem Scheitelpunkt in aufsteigender Reihenfolge der Weglänge zwischen jedem Scheitelpunkt und dem Quellpunkt v zu generieren. Das heißt, suchen Sie zuerst den kürzesten Weg mit der kürzesten Länge und verwenden Sie ihn dann, um den kürzesten Weg mit der nächstkürzesten Länge usw. zu finden, bis alle kürzesten Wege vom Quellpunkt v zu anderen Eckpunkten gefunden sind.
Die Code-Implementierung ist wie folgt:
package com.algorithm.impl; public class Dijkstra { private static int M = 10000; //Diese Straße ist blockiert public static void main(String[] args) { int[][] Weight1 = {//Adjacency Matrix {0, 3 ,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] Weight2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; int start=0; dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("Der kürzeste Abstand von „+start+“ zu „+i+“ ist: „+shortPath[i ] ); } public static int[] dijkstra(int[][]weight, int start) { //Akzeptiert eine Gewichtsmatrix eines gerichteten Graphen und eine Startpunktnummer start (nummeriert von 0, der Scheitelpunkt wird im Array gespeichert) //Gibt ein int[]-Array zurück, das die Länge des kürzesten Pfades vom Start dorthin angibt int n = Weight.length ; //Anzahl der Eckpunkte int[] shortPath = new int[n]; //Speichern Sie den kürzesten Pfad vom Start zu anderen Punkten String[] path = new String[n]; Pfad vom Start zu anderen Punkten String-Darstellung for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] besuchte = new int[n]; //Markieren Sie, ob der kürzeste Pfad zum aktuellen Scheitelpunkt ist wurde gefunden, 1 bedeutet, dass es gefunden wurde //Initialisierung, der erste Scheitelpunkt wurde gefunden shortPath[start] = 0; besuchte[start] = 1; for(int count = 1; count < n; count++) { //So fügen Sie n-1 Scheitelpunkte hinzu int k = -1; //Wählen Sie einen nicht markierten Scheitelpunkt aus, der dem Anfangsscheitelpunkt am nächsten liegt int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited [i] == 0 && Gewicht[Start][i] < dmin) { dmin = Gewicht[Start][i] } } //Markieren Sie den neu ausgewählten Scheitelpunkt als den kürzesten Pfad, der gefunden wurde, und der kürzeste Pfad zum Starten ist dmin shortPath[k] = dminvisit[k] = 1; //Korrigieren Sie den Pfad von start to Entfernung nicht besuchter Punkte for(int i = 0; i < n; i++) { if(visited[i] == 0 && Weight[Start][k] + Weight[k][i] < Weight[Start] [ich]) { Gewicht[Start][i] = Gewicht[Start][k] + Gewicht[k][i]; Pfad[i] = Pfad[k] + "-->" + i; 0; i < n; i++) { System.out.println("Der kürzeste Pfad von „+start+“ zu „+i+“ ist: „+path[i] } System.out.println("================================="); }}Das Ergebnis der Ausführung dieses Programms ist:
Der kürzeste Weg von 0 nach 0 ist: 0-->0 Der kürzeste Weg von 0 nach 1 ist: 0-->1 Der kürzeste Weg von 0 nach 2 ist: 0-->3-->2 von Der kürzeste Weg von 0 nach 3 ist: 0-->3 Der kürzeste Weg von 0 nach 4 ist: 0-->3-->2-->4==== ================================ Der kürzeste Abstand von 0 nach 0 ist: 0 von 0 nach 1 Der kürzeste Abstand von 0 nach 2 beträgt: 50. Der kürzeste Abstand von 0 nach 3 beträgt: 30. Der kürzeste Abstand von 0 nach 4 beträgt: 60