L’algorithme de Dijkstra : Un guide complet pour le plus court chemin

Par /

L’algorithme de Dijkstra, du nom de son inventeur Edsger W. Dijkstra, est l’un des algorithmes les plus populaires en informatique pour résoudre le problème du plus court chemin. Il trouve son utilité dans divers domaines, notamment la cartographie, la planification de réseaux, la navigation GPS et bien d’autres. Dans cet article, nous allons plonger en profondeur dans cet algorithme, expliquer son fonctionnement, fournir des exemples de code en Python, et explorer ses applications pratiques.

Fonctionnement de l’algorithme de Dijkstra

L’algo de Dijkstra résout le problème du plus court chemin à partir d’un nœud source vers tous les autres nœuds d’un graphe pondéré. Voici comment il fonctionne :

  • Commencez par initialiser un tableau de distance avec une valeur infinie pour tous les nœuds, sauf le nœud source, pour lequel la distance est mise à zéro.
  • Choisissez le nœud avec la plus petite distance non encore traitée.
  • Mettez à jour les distances de ses voisins en explorant les chemins possibles à partir du nœud actuel.
  • Répétez ces étapes pour tous les nœuds jusqu’à ce que tous les nœuds soient marqués comme traités.

À la fin de l’algorithme, le tableau de distance contiendra les distances minimales de chaque nœud au nœud source, et un chemin optimal peut être reconstruit en suivant les prédécesseurs à partir du nœud de destination.

Exemple de code en Python

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [start]
    
    while queue:
        current_node = queue.pop(0)
        
        for neighbor, weight in graph[current_node].items():
            distance = distances[current_node] + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                queue.append(neighbor)
    
    return distances

Cet exemple de code Python illustre la mise en œuvre de l’algorithme de Dijkstra. Vous pouvez l’utiliser avec un graphe représenté sous forme de dictionnaire où les clés sont les nœuds et les valeurs sont des dictionnaires indiquant les voisins et les poids des arêtes.

algorithme de dijkstra
import matplotlib.pyplot as plt
import numpy as np

# Define the graph as an adjacency matrix
graph = np.array([
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0]
])

# Dijkstra's algorithm
def dijkstra(graph, start):
    num_vertices = len(graph)
    shortest_distance = [float("inf")] * num_vertices
    shortest_distance[start] = 0
    visited = [False] * num_vertices

    for _ in range(num_vertices):
        min_distance = float("inf")
        min_index = -1

        for v in range(num_vertices):
            if not visited[v] and shortest_distance[v] < min_distance:
                min_distance = shortest_distance[v]
                min_index = v

        visited[min_index] = True

        for v in range(num_vertices):
            if not visited[v] and graph[min_index][v] > 0:
                if shortest_distance[min_index] + graph[min_index][v] < shortest_distance[v]:
                    shortest_distance[v] = shortest_distance[min_index] + graph[min_index][v]

    return shortest_distance

# Starting node
start_node = 0

# Run Dijkstra's algorithm
shortest_distances = dijkstra(graph, start_node)

# Visualize the graph
plt.figure(figsize=(8, 6))
plt.imshow(graph, cmap='viridis', interpolation='nearest')
plt.colorbar(label='Edge Weight')
plt.title("Graph Visualization")
plt.xlabel("Nodes")
plt.ylabel("Nodes")

# Annotate nodes with their shortest distances
for i, distance in enumerate(shortest_distances):
    plt.text(i, i, f"0", color='red', ha='center', va='center', fontsize=12, fontweight='bold')
    if distance != float("inf"):
        plt.text(i, i, f"{distance}", color='white', ha='center', va='center', fontsize=12, fontweight='bold')

# Show the plot
plt.show()

algorithme de dijkstra

Applications de l’algorithme de Dijkstra

L’algorithme de Dijkstra est largement utilisé dans de nombreuses applications, notamment :

  • Calcul de l’itinéraire le plus court dans les systèmes de navigation GPS.
  • Planification de réseaux de télécommunications.
  • Optimisation de la gestion des réseaux informatiques.
  • Routage de paquets dans les réseaux informatiques.
  • Calcul de la distance la plus courte dans les systèmes de cartographie.

Liens externes et internes

Pour en savoir plus sur l’algorithme de Dijkstra et son utilisation, vous pouvez consulter les ressources suivantes :

N’hésitez pas à explorer ces liens pour approfondir vos connaissances sur l’algorithme de Dijkstra et son utilisation dans divers domaines.

Conclusion

L’algorithme de Dijkstra est un outil puissant pour résoudre le problème du plus court chemin dans divers contextes. En comprenant son fonctionnement et en utilisant des exemples de code comme celui présenté ici, vous serez en mesure de l’appliquer efficacement à vos propres projets. En explorant les liens externes et internes fournis, vous pouvez approfondir vos connaissances et découvrir des applications avancées de cet algorithme essentiel.

Pour approfondir votre compréhension de l’algo de Dijkstra, vous pouvez consulter des ressources supplémentaires sur des sites réputés :

Retour en haut