Algorithmes de recherche du plus court chemin

9.1 Principes de fonctionnement de l'algorithme de Dijkstra

L'algorithme de Dijkstra est un algorithme pour trouver les plus courts chemins depuis le sommet initial jusqu'à tous les autres sommets d'un graphe avec des poids d'arêtes non négatifs. L'algorithme utilise une approche gloutonne, choisissant à chaque étape le sommet avec la plus petite distance connue depuis le sommet initial et mettant à jour les distances jusqu'aux sommets voisins.

Étapes de l'algorithme :

1. Initialisation :

• On fixe la distance jusqu'au sommet initial à 0.
• On fixe la distance jusqu'à tous les autres sommets à l'infini.
• On crée un ensemble de sommets non visités.

2. Choix du sommet actuel :

• On choisit un sommet non visité ayant la plus petite distance (le sommet initial au premier pas).

3. Mise à jour des distances :

• Pour chaque sommet voisin du sommet actuel, si le nouveau chemin via le sommet actuel est plus court que le chemin connu, on met à jour la distance jusqu'à ce sommet.

4. Marquage du sommet actuel comme visité :

• On supprime le sommet actuel de l'ensemble des sommets non visités.

5. On répète les étapes 2-4, jusqu'à ce que tous les sommets soient visités ou jusqu'à ce qu'on atteigne le sommet cible.

Complexité temporelle et spatiale de l'algorithme de Dijkstra :

Complexité temporelle :

O((V + E) log V) en utilisant une file de priorité (par exemple, un tas de Fibonacci), où V est le nombre de sommets, E est le nombre d'arêtes.

O(V^2) en utilisant une simple liste pour stocker les distances.

Complexité spatiale :

O(V) pour stocker les distances et les ancêtres (pour reconstituer le chemin).

9.2 Implémentation de l'algorithme de Dijkstra

L'implémentation de l'algorithme de Dijkstra est longue, mais très simple. Je te recommande d'essayer de la comprendre. Si ce n'est pas clair, remonte un peu plus haut et relis les étapes principales de l'algorithme.

Exemple d'implémentation de l'algorithme de Dijkstra en utilisant une file de priorité (tas) :

import heapq

def dijkstra(graph, start):
    # Initialisation
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    parents = {vertex: None for vertex in graph}
            
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
            
        # Si la distance actuelle est plus grande que celle enregistrée, on passe au sommet suivant
        if current_distance > distances[current_vertex]:
            continue
            
        # Mise à jour des distances pour les sommets voisins
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            # Si un chemin plus court vers le sommet voisin est trouvé
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parents[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
            
    return distances, parents
            
# Exemple d'utilisation :
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
start_vertex = 'A'
distances, parents = dijkstra(graph, start_vertex)
print("Les distances les plus courtes depuis le sommet de départ :", distances)
print("Les ancêtres pour reconstituer le chemin :", parents)

Sortie :

Les distances les plus courtes depuis le sommet de départ : {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Les ancêtres pour reconstituer le chemin : {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}

9.3 Exemples de problèmes résolus avec l'algorithme de Dijkstra

Exemples classiques de problèmes résolus avec l'algorithme de Dijkstra :

1. Optimisation des itinéraires dans les réseaux de transport

Trouver le plus court chemin entre des points dans un réseau de transport (par exemple, entre des villes).

Application :

Les systèmes de navigation, comme Google Maps, utilisent l'algorithme de Dijkstra pour calculer les itinéraires optimaux.

2. Planification des itinéraires de livraison

Optimisation des itinéraires pour les services de livraison de marchandises, afin de minimiser les coûts et le temps de livraison.

Application :

Les entreprises de logistique utilisent l'algorithme de Dijkstra pour planifier les itinéraires de livraison et réduire les coûts opérationnels.

3. Gestion des réseaux

Optimisation du routage des paquets de données dans les réseaux informatiques pour minimiser les retards et augmenter la bande passante.

Application :

Les protocoles de routage, tels que OSPF (Open Shortest Path First), utilisent l'algorithme de Dijkstra pour trouver les plus courts chemins dans les réseaux.

4. Analyse des réseaux sociaux

Trouver les plus courts chemins et mesurer la centralité dans les graphes sociaux (par exemple, pour identifier les utilisateurs les plus influents).

Application :

Les plateformes sociales analysent les connexions entre utilisateurs pour fournir des recommandations et analyser l'activité réseau.

5. Jeux et mondes virtuels

Trouver le chemin pour les personnages dans les mondes de jeu avec des obstacles et différents niveaux de difficulté.

Application :

Les moteurs de jeu utilisent l'algorithme de Dijkstra pour calculer les déplacements des personnages et des objets dans les mondes virtuels.

6. Systèmes de gestion de l'énergie

Optimisation de la distribution de l'énergie dans les réseaux électriques pour minimiser les pertes et assurer la fiabilité des approvisionnements.

Application :

Les compagnies d'électricité utilisent l'algorithme de Dijkstra pour optimiser les routes de transmission d'énergie dans les réseaux, afin de minimiser les pertes d'énergie et éviter les surcharges.

Exemple :

Dans les réseaux électriques, chaque nœud représente une sous-station, et les arêtes sont des lignes de transmission avec différents niveaux de résistance. L'algorithme de Dijkstra aide à trouver le chemin avec la moindre résistance de la source d'énergie au consommateur.

7. Systèmes d'évacuation et planification de chemin

Optimisation des itinéraires d'évacuation dans les bâtiments ou les villes pour un retrait rapide et sécurisé des gens en cas d'urgence.

Application :

Les architectes et ingénieurs utilisent l'algorithme de Dijkstra pour planifier les itinéraires d'évacuation, afin de garantir un retrait sûr et rapide des personnes des zones dangereuses.

Exemple :

Dans un immeuble résidentiel ou un immeuble de bureaux, les nœuds du graphe représentent les chambres et les couloirs, et les arêtes sont les trajets entre eux. L'algorithme de Dijkstra peut être utilisé pour trouver le chemin le plus court depuis n'importe quel point du bâtiment vers la sortie la plus proche.