Einführung
In diesem Lab implementieren wir Dijkstras Algorithmus in Java. Dijkstras Algorithmus ist ein populärer Algorithmus, der zur Lösung des kürzesten Wegproblems für einen gewichteten Graphen verwendet wird.
💡 Dieser Artikel wurde von AI-Assistenten übersetzt. Um die englische Version anzuzeigen, können Sie hier klicken
In diesem Lab implementieren wir Dijkstras Algorithmus in Java. Dijkstras Algorithmus ist ein populärer Algorithmus, der zur Lösung des kürzesten Wegproblems für einen gewichteten Graphen verwendet wird.
In diesem Schritt erstellen wir eine Klasse namens Graph, die unseren gewichteten Graphen repräsentieren wird. Wir werden in dieser Klasse eine 2D Adjazenzmatrix erstellen, um die Kanten des Graphen zu repräsentieren.
class Graph
{
int[][] adjMatrix; // Adjazenzmatrix, um die Kanten zu repräsentieren
int numOfvertices;
Graph(int[][] mat, int v)
{
this.adjMatrix = mat;
this.numOfvertices = v;
}
void addEdge(int src, int dest, int edgeWeight)
{
adjMatrix[src][dest] = edgeWeight;
adjMatrix[dest][src] = edgeWeight;
}
}
In diesem Schritt implementieren wir Dijkstras Algorithmus in Java. Erstellen wir eine Hilfsmethode namens getClosestVertex, um den nächsten nicht besuchten Knoten zu finden. Wir implementieren auch den Hauptalgorithmus in einer dijkstrasShortestPath-Methode. Diese Methode nimmt einen Graphen und einen Quellknoten als Parameter und gibt das Array der kürzesten Distanzen zurück.
public static int getClosestVertex(int[] distance, boolean[] visited) {
int min = Integer.MAX_VALUE;
int minIdx = -1;
for(int i=0; i<distance.length; i++) {
if(distance[i] < min)
if(visited[i] == false) {
min = distance[i];
minIdx = i;
}
}
return minIdx;
}
public static int[] dijkstrasShortestPath(Graph g, int src) {
// endgültiges Array der kürzesten Distanzen
int[] distance = new int[g.numOfvertices];
// Array, um anzuzeigen, ob die kürzeste Distanz eines Knotens gefunden wurde
boolean[] visited = new boolean[g.numOfvertices];
// Initialisierung der Arrays
for(int i=0; i<g.numOfvertices; i++) {
distance[i] = Integer.MAX_VALUE; // Anfangsdistanz ist unendlich
visited[i] = false; // Die kürzeste Distanz für keinen Knoten wurde noch gefunden
}
distance[src] = 0;
for(int i=0; i<g.numOfvertices; i++) {
int closestVertex = getClosestVertex(distance, visited); // hole den nächsten Knoten
if(closestVertex == Integer.MAX_VALUE) // Wenn der nächste Knoten unendlich weit entfernt ist, bedeutet das, dass kein anderer Knoten erreicht werden kann. Also return
return distance;
visited[closestVertex] = true;
for(int j=0; j<g.numOfvertices; j++) {
if(visited[j] == false) // Die kürzeste Distanz des Knotens j sollte noch nicht finalisiert sein
{
if(g.adjMatrix[closestVertex][j]!= 0) {
int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
if(d < distance[j]) // Die Distanz über closestVertex ist kleiner als die Anfangsdistanz
distance[j] = d;
}
}
}
}
return distance;
}
In diesem Schritt testen wir unsere Implementierung, indem wir eine main-Methode erstellen, die Kanten zu unserem Graphen hinzufügt und unsere dijkstrasShortestPath-Methode aufruft, um die kürzeste Distanz von einem Quellknoten zu allen anderen Knoten eines gewichteten Graphen zu finden.
public static void main(String[] args) {
int numOfVertices = 6;
int[][] adjMat = new int[6][6];
Graph graph = new Graph(adjMat, numOfVertices);
// füge Kanten zum Graphen hinzu
graph.addEdge(0, 4, 21);
graph.addEdge(0, 3, 18);
graph.addEdge(2, 1, 7);
graph.addEdge(1, 4, 6);
graph.addEdge(4, 5, 10);
graph.addEdge(4, 3, 11);
graph.addEdge(5, 3, 7);
// rufe Dijkstras Algorithmus auf, um die kürzeste Distanz zu finden
int[] dist = dijkstrasShortestPath(graph, 0);
System.out.print(Arrays.toString(dist));
}
Kompilieren und ausführen Sie den obigen Code, um das Array der kürzesten Distanzen [0, 27, 34, 18, 21, 25] zu erhalten.
Herzlichen Glückwunsch! Sie haben das Lab "Implementing Dijkstra's Algorithm" abgeschlossen. Sie können in LabEx weitere Labs absolvieren, um Ihre Fähigkeiten zu verbessern.