Implementierung von Dijkstras Algorithmus

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.

Skills Graph

Erstellen einer Graph-Klasse

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

Implementieren von Dijkstras Algorithmus

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

Testen unserer Implementierung

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.

Zusammenfassung

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.