Implémentation de l'algorithme de Dijkstra

Introduction

Dans ce laboratoire, nous allons implémenter l'algorithme de Dijkstra en Java. L'algorithme de Dijkstra est un algorithme populaire utilisé pour résoudre le problème du plus court chemin dans un graphe pondéré.

Créer une classe Graph

Dans cette étape, nous allons créer une classe appelée Graph qui représentera notre graphe pondéré. Nous allons créer une matrice d'adjacence 2D dans cette classe pour représenter les arêtes du graphe.

class Graph
{
    int[][] adjMatrix; // matrice d'adjacence pour représenter les arêtes
    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;
    }
}

Implémenter l'algorithme de Dijkstra

Dans cette étape, nous allons implémenter l'algorithme de Dijkstra en Java. Créons une méthode d'aide appelée getClosestVertex pour trouver le nœud non visité le plus proche. Nous allons également implémenter l'algorithme principal dans une méthode dijkstrasShortestPath. Cette méthode prendra un Graph et un sommet source en paramètres et renverra le tableau des plus courtes distances.

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) {
    // tableau final des plus courtes distances
    int[] distance = new int[g.numOfvertices];
    // tableau pour indiquer si la plus courte distance d'un sommet a été trouvée
    boolean[] visited = new boolean[g.numOfvertices];

    // initialisation des tableaux
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // distance initiale est infinie
        visited[i] = false; // la plus courte distance pour un nœud quelconque n'a pas été trouvée encore
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // obtenir le nœud le plus proche
        if(closestVertex == Integer.MAX_VALUE) // si le nœud le plus proche est à une distance infinie, cela signifie qu'aucun autre nœud ne peut être atteint. Donc retourner
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // la plus courte distance du nœud j ne devrait pas avoir été définitivement déterminée
            {
                if(g.adjMatrix[closestVertex][j]!= 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // la distance via closestVertex est inférieure à la distance initiale
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

Tester notre implémentation

Dans cette étape, nous allons tester notre implémentation en créant une méthode main qui ajoutera des arêtes à notre graphe et appellera notre méthode dijkstrasShortestPath pour trouver la plus courte distance d'un sommet source à tous les autres sommets d'un graphe pondéré.

public static void main(String[] args) {
    int numOfVertices = 6;
    int[][] adjMat = new int[6][6];
    Graph graph = new Graph(adjMat, numOfVertices);

    // ajouter des arêtes au graphe
    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);

    // appeler l'algorithme de Dijkstra pour trouver la plus courte distance
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

Compilez et exécutez le code ci-dessus pour obtenir le tableau des plus courtes distances [0, 27, 34, 18, 21, 25].

Résumé

Félicitations ! Vous avez terminé le laboratoire sur l'implémentation de l'algorithme de Dijkstra. Vous pouvez pratiquer d'autres laboratoires sur LabEx pour améliorer vos compétences.