Mise en œuvre de l'algorithme de Dijkstra pour la recherche de chemins optimaux dans les graphes avec Java

Introduction

L’algorithme de Dijkstra est un algorithme de recherche de chemins dans les graphes qui permet de trouver le chemin le plus court entre deux nœuds. Il est utilisé dans de nombreux domaines, tels que la navigation GPS, la planification de routes et la recherche de chemins optimaux dans les réseaux de transport.

Principe de l’algorithme de Dijkstra

L’algorithme de Dijkstra fonctionne en attribuant une distance à chaque nœud du graphe, qui représente la distance minimale entre le nœud de départ et le nœud actuel. L’algorithme itère ensuite sur les nœuds du graphe, en mettant à jour les distances et en sélectionnant le nœud avec la distance minimale comme prochain nœud à traiter.

Mise en œuvre de l’algorithme de Dijkstra en Java

Voici un exemple de mise en œuvre de l’algorithme de Dijkstra en Java :

import java.util.*;

public class Dijkstra {
    private static class Nœud {
        int id;
        int distance;
        Nœud précédent;

        public Nœud(int id) {
            this.id = id;
            this.distance = Integer.MAX_VALUE;
            this.précédent = null;
        }
    }

    public static List<Nœud> dijkstra(List<Nœud> nœuds, int nœudDeDépart) {
        // Initialisation des distances
        for (Nœud nœud : nœuds) {
            nœud.distance = Integer.MAX_VALUE;
        }
        nœuds.get(nœudDeDépart).distance = 0;

        // Sélection du nœud avec la distance minimale
        Nœud nœudActuel = nœuds.get(nœudDeDépart);
        while (nœudActuel != null) {
            // Mise à jour des distances des nœuds voisins
            for (Nœud voisin : getVoisins(nœudActuel, nœuds)) {
                int nouvelleDistance = nœudActuel.distance + getDistance(nœudActuel, voisin);
                if (nouvelleDistance < voisin.distance) {
                    voisin.distance = nouvelleDistance;
                    voisin.précédent = nœudActuel;
                }
            }

            // Sélection du nœud avec la distance minimale
            nœudActuel = getNœudAvecDistanceMinimale(nœuds);
        }

        // Reconstruction du chemin
        List<Nœud> chemin = new ArrayList<>();
        nœudActuel = nœuds.get(nœudDeDépart);
        while (nœudActuel != null) {
            chemin.add(nœudActuel);
            nœudActuel = nœudActuel.précédent;
        }
        Collections.reverse(chemin);
        return chemin;
    }

    private static List<Nœud> getVoisins(Nœud nœud, List<Nœud> nœuds) {
        // Récupération des nœuds voisins
        List<Nœud> voisins = new ArrayList<>();
        for (Nœud autreNœud : nœuds) {
            if (autreNœud != nœud && estVoisin(nœud, autreNœud)) {
                voisins.add(autreNœud);
            }
        }
        return voisins;
    }

    private static int getDistance(Nœud nœud1, Nœud nœud2) {
        // Récupération de la distance entre deux nœuds
        // À implémenter en fonction du type de graphe
        return 1;
    }

    private static boolean estVoisin(Nœud nœud1, Nœud nœud2) {
        // Vérification si deux nœuds sont voisins
        // À implémenter en fonction du type de graphe
        return true;
    }

    private static Nœud getNœudAvecDistanceMinimale(List<Nœud> nœuds) {
        // Récupération du nœud avec la distance minimale
        Nœud nœudAvecDistanceMinimale = null;
        for (Nœud nœud : nœuds) {
            if (nœud.distance < Integer.MAX_VALUE && (nœudAvecDistanceMinimale == null || nœud.distance < nœudAvecDistanceMinimale.distance)) {
                nœudAvecDistanceMinimale = nœud;
            }
        }
        return nœudAvecDistanceMinimale;
    }
}

Exemple d’utilisation

Voici un exemple d’utilisation de l’algorithme de Dijkstra pour trouver le chemin le plus court entre deux nœuds dans un graphe :

public static void main(String[] args) {
    List<Nœud> nœuds = new ArrayList<>();
    nœuds.add(new Nœud(0));
    nœuds.add(new Nœud(1));
    nœuds.add(new Nœud(2));
    nœuds.add(new Nœud(3));

    // Définition des distances entre les nœuds
    // À implémenter en fonction du type de graphe

    List<Nœud> chemin = dijkstra(nœuds, 0);
    System.out.println("Chemin le plus court : ");
    for (Nœud nœud : chemin) {
        System.out.println(nœud.id);
    }
}

Notez que les méthodes getVoisins, getDistance et estVoisin doivent être implémentées en fonction du type de graphe utilisé.