L'algorithme de Dijkstra dans Python & C++ (Exemple)

Quel est le chemin le plus court ou la distance la plus courte ?

Le chemin le plus court, ou chemin de distance minimale, relie un sommet source à un sommet destination. En théorie des graphes, plusieurs chemins sont possibles entre une source et une destination. Parmi ces chemins, s'il en existe un dont le coût est minimal, on l'appelle le chemin le plus court.

Ici, le terme « coût » désigne le nombre de nœuds du chemin ou la somme des coûts de chaque arête. Un chemin peut comporter une ou plusieurs arêtes. La connexion entre deux sommets est appelée « arête ». Il existe différents algorithmes de calcul du plus court chemin, tels que l'algorithme de Dijkstra et l'algorithme de Bellman-Ford.

Nous allons ici aborder l'algorithme de Dijkstra. Prenons l'exemple du graphe pondéré suivant :

Un graphique non pondéré

• Le terme « pondéré » désigne le coût du déplacement d'un nœud à un autre. Par exemple, pour passer du nœud 1 au nœud 2, le coût ou poids est de 1.
• Le chemin entre le nœud 1 et le nœud 2 est appelé l'arête.
• « Non orienté » signifie que vous pouvez passer d'un nœud à un autre et revenir au nœud précédent. Ainsi, si nous cherchons tous les itinéraires du nœud 1 au nœud 7, ils seront :

Parmi ces quatre itinéraires, on constate que le premier coûte 7. C'est donc le chemin le plus court en termes de coût.

Le plus court chemin

Comment fonctionne l'algorithme de Dijkstra

L'algorithme de Dijkstra permet de trouver le chemin le plus court dans les graphes pondérés, orientés ou non. Cet algorithme est dit glouton car il choisit systématiquement le nœud le plus proche de l'origine. Le terme « glouton » signifie que, parmi plusieurs résultats possibles, l'algorithme sélectionne le meilleur.

Ici, nous cherchons à trouver les chemins les plus courts parmi tous les itinéraires possibles. L'algorithme de Dijkstra trouve donc tous les chemins les plus courts à partir d'un nœud source unique. Par conséquent, il se comporte comme un… algorithme gourmand.

Dans la section « exemple » ci-dessous, vous trouverez la démarche étape par étape. Elle fonctionne comme suit :

Étape 1) Initialisez le nœud de départ avec un coût de 0 et les autres nœuds avec un coût infini.
Étape 2) Conservez un tableau ou une liste pour conserver track des nœuds visités.
Étape 3) Mettez à jour le coût du nœud avec le coût minimal. Cela peut se faire en comparant le coût actuel avec le coût du chemin (comme illustré dans l'exemple).
Étape 4) Poursuivez l'étape 3 jusqu'à ce que tous les nœuds soient visités.

Après avoir complété toutes ces étapes, nous trouverons le chemin qui coûte le moins cher de la source à la destination.

Différence entre Dijkstra et BFS, DFS

La principale différence entre l'algorithme de Dijkstra et les algorithmes BFS et DFS réside dans leur nature : Dijkstra est un algorithme de recherche du plus court chemin, tandis que BFS et DFS sont des algorithmes de recherche de chemin général. En règle générale, BFS et DFS ne tiennent pas compte du coût des arêtes lors de la recherche du chemin. Par conséquent, ces algorithmes ne garantissent pas de trouver le chemin le plus court.

Démonstration sur une grille 2D du fonctionnement de la recherche en largeur (BFS)

Algosketch, montrant la démonstration BFS

Cette démonstration indique que BFS trouve uniquement le chemin. Toutefois, il ne se soucie pas du poids du chemin. BFS (Recherche en largeur d'abord) suppose que voyager d’un nœud à un autre ne coûtera que 1.

Prenons l'exemple d'un graphique :

Ici, le parcours en largeur (BFS) trouve un chemin au niveau 2. Le parcours en largeur parcourt le graphe niveau par niveau. Il se déroule donc comme suit :

Étape 1) Commencez par le nœud « 1 » et visitez tous les nœuds adjacents 2, 3, 4.

Étape 2) Marquez les nœuds 2, 3 et 4 comme étant de niveau 1 et visitez leurs nœuds adjacents. L'exploration se poursuivra jusqu'à atteindre le nœud de destination.

En termes de DFS, il parcourra le chemin de 1 à 7 comme suit :

• 1 → 2 → 3 → 7 (coût initial 10, coût DFS 3)
• 1 → 2 → 6 → 7 (coût initial 7, coût DFS 3)
• 1 → 3 → 7 (coût initial 8, coût DFS 2)
• 1 → 4 → 5 → 7 (coût initial 13, coût DFS 3)

Comme on le voit, le parcours en profondeur (DFS) calcule le coût de son chemin en fonction du nombre d'arêtes. Le DFS procède comme suit :

• DFS peut trouver un chemin depuis la source (sommet de départ) jusqu'à la destination.
• Il ne peut pas garantir si le chemin découvert du nœud source à la destination est le chemin le plus court ou non.

Cependant, l'algorithme de Dijkstra sélectionne les arêtes en fonction de leur coût. Étant un algorithme glouton, il choisit les chemins de coût minimal.

Exemple de l'algorithme de Dijkstra

L'algorithme de Dijkstra utilise le coût ou le poids pour calculer le coût total du chemin.

L'objectif de l'algorithme de Dijkstra est de minimiser ce coût ou ce poids total. Dans l'exemple ci-dessus, nous trouvons les meilleurs chemins du nœud 1 au nœud 7, puis calculons tous les coûts.

L'algorithme de Dijkstra trouve les plus courts chemins en calculant des poids. Il ne recherche pas tous les chemins possibles. Prenons un exemple pour illustrer son fonctionnement : supposons que l'on vous demande de trouver le plus court chemin du nœud 1 au nœud 7.

Pour ce processus, les étapes sont indiquées ci-dessous :

Étape 1) Initialisez le coût du nœud de départ à 0. Attribuez « Inf » pour les autres nœuds. Cela signifie qu'il n'existe aucun chemin entre la source et le nœud, ou que ce chemin n'a pas encore été parcouru.

Étape 2) Lorsque vous sélectionnez le nœud 1, il est marqué comme visité. Mettez ensuite à jour tous les nœuds voisins du nœud 1. Les nœuds 2, 3 et 4 sont les nœuds voisins du nœud 1.

Lors de la mise à jour d'un coût, nous devons suivre la procédure ci-dessous :

Nous pouvons mettre à jour le coût de chaque nœud à l'aide de la formule ci-dessus. Par exemple, nous étions au nœud 1 et nous devions mettre à jour le coût de ses nœuds adjacents 2, 3 et 4. Après la mise à jour, les coûts se présenteront comme suit :

Étape 3) Pour le nœud « 2 », les voisins sont 6 et 3. Nous mettons à jour le coût du nœud « 6 » en comparant l’infini (valeur actuelle) avec le coût du nœud 2 plus le coût du chemin de 2 à 6. Autrement dit, le nœud « 6 » aura un coût de 1+3, soit 4.

Le nœud 3 est voisin du nœud 2. Cependant, nous avons calculé son coût à l'étape précédente, qui était de 7. Maintenant, si notre chemin est 1-2-3, le nœud 3 aura un coût de 10. Chemin 1-2- 3 coûtera 10, tandis que 1 à 3 coûtera 7.

Étape 4) Pour le nœud 3, le nœud voisin est 7. En comparant la valeur actuelle du nœud 7 avec le coût du chemin (7+1), soit 8, on met à jour le coût du nœud 7, qui est de 8. On trouve donc un chemin du nœud 1 au nœud 7 : 1→3→7. Son coût est de 8.

Étape 5) Pour le nœud 4, nous mettrons à jour le coût de son nœud adjacent en conséquence. Ainsi, le coût du nœud « 5 » sera mis à jour à 8. Après les étapes 4 et 5, le résultat sera le suivant :

Le chemin 1-3-7 a un coût de 8 (précédemment). Le nœud 7 n'a pas été marqué comme visité car il est accessible depuis le nœud 6. Le chemin 1-2-6 avait un coût de 4. Le chemin 1-2-6-7 aura donc un coût de 7.

Comme 7 < 8, le chemin le plus court du sommet source « 1 » au sommet destination « 7 » sera 1-2-6-7, et son coût est de 7. Auparavant, il était 1-3-7, et son coût était de 8. Le graphe final ressemblera donc à ceci :

Le bord marqué d'une ligne noire est notre chemin le plus court de 1 à 7, et il nous en coûtera 7.

Faux Code L'algorithme de Dijkstra

Voici le pseudo-code de l'algorithme de Dijkstra :

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Implémentation de l'algorithme de Dijkstra

Pour implémenter l'algorithme de Dijkstra en utilisant C++Voici le code :

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] && distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] && graph[U][j] &&
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

Sortie :

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

Python Implémentation de l'algorithme de Dijkstra

Pour implémenter l'algorithme de Dijkstra en utilisant PythonVoici le code :

num_of_vertex = 7
def minimumDistance(distance, visited):
    _min = 1e11
    min_index = 1e11
    for i in range(num_of_vertex):
        if not visited[i] and distance[i] <= _min:
            _min = distance[i]
            min_index = i
    return min_index

def printParentNode(parent, i):
    if parent[i] == -1:
        return
    printParentNode(parent, parent[i])
    print("{} ".format(i + 1), end="")

def dijkstra(graph, src):
    distance = list()
    visited = list()
    parent = list()
    for i in range(num_of_vertex):
        parent.append(-1)
        distance.append(1e11)
        visited.append(False)
    distance[src] = 0
    for i in range(num_of_vertex - 1):
        U = minimumDistance(distance, visited)
        visited[U] = True
        for j in range(num_of_vertex):
            curr_distance = distance[U] + graph[U][j]
            if not visited[j] and graph[U][j] and curr_distance < distance[j]:
                parent[j] = U
                distance[j] = curr_distance
    print("Vertex\t\tDistance\tPath")
    for i in range(num_of_vertex):
        print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end="")
        printParentNode(parent, i)
        print("")

graph = [
    [0, 1, 7, 6, 0, 0, 0],
    [1, 0, 9, 0, 0, 3, 0],
    [7, 9, 0, 0, 0, 0, 1],
    [6, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 3],
    [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

Sortie :

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

On peut constater que l'algorithme calcule la distance la plus courte à partir du nœud source.

Application de l'algorithme de Dijkstra

L'algorithme de Dijkstra a de nombreuses applications. Parmi celles-ci, il est largement utilisé dans le domaine des réseaux. Voici quelques exemples concrets d'utilisation de l'algorithme de Dijkstra :

Dijkstra dans Google Plans: Cet algorithme constitue la base de la recherche des chemins les plus courts, comme nous pouvons le constater dans l'extrait de code ci-dessus.

Google n'utilise pas l'algorithme de Dijkstra simple. Il utilise plutôt une version modifiée. Lorsque vous sélectionnez une destination, il vous affiche plusieurs chemins possibles. Google Cartes. Parmi ces itinéraires, certains sont triés pour l'utilisateur. Ces itinéraires sont sélectionnés en fonction du « temps ». Ainsi, le « temps » représente le coût du parcours le plus court.

Dijkstra dans le routage IP : Routage IP Le terme « routage » désigne un terme de réseau. Il décrit comment un paquet de données est acheminé jusqu'à son destinataire via différents chemins. Ces chemins comprennent des routeurs, des serveurs et d'autres équipements. Le routage IP utilise différents protocoles.

Ces protocoles aident le routeur à trouver les chemins les plus courts pour acheminer les données. L'un d'eux est OSPF (Open Shortest Path First). OSPF utilise l'algorithme de Dijkstra. Le routeur maintient une table de routes. Chaque routeur partage sa table avec ses voisins. Après réception de la table mise à jour, il doit recalculer tous les chemins. C'est alors que le routeur utilise l'algorithme de Dijkstra.

Limitation de l'algorithme de Dijkstra

L'algorithme de Dijkstra ne garantit pas le chemin le plus court dans un graphe comportant des arêtes négatives. Il repose sur les principes suivants :

• Un chemin le plus court sera emprunté d’un nœud à un autre.
• Une fois le chemin le plus court entre deux nœuds sélectionné, il ne sera plus calculé.

Ici, remarquez deux exemples avec des bords négatifs.

Dans le graphique de gauche, Il y a trois sommets. L'algorithme de Dijkstra s'exécutera sur le graphe comme suit :

Étape 1) Le sommet de départ « 1 » sera initialisé à zéro. Les autres nœuds auront l'infini.

Étape 2) Marquez le nœud « 1 » comme visité et incluez-le dans le chemin le plus court.

Étape 3) La distance entre le nœud source 1 et les nœuds 2 et 3 est initialement fixée à l'infini, car le chemin le plus court n'a pas encore été calculé. Par conséquent, tout chemin de coût inférieur à l'infini sera ajouté au chemin le plus court (approche gloutonne).

Étape 4) Mise à jour de la distance entre le sommet source « 1 » et le sommet « 2 ». Le poids actuel est de 5 (5 < ∞). De même, mise à jour de la distance entre le nœud « 1 » et le sommet « 3 » avec un poids de 3.

Étape 5) Si l'on vérifie les distances les plus courtes à partir du nœud « 1 », on constate que 5 est la distance la plus courte pour l'arête 1→2. Le nœud « 2 » sera donc marqué comme visité. De même, le nœud « 3 » sera également marqué comme visité, car la distance la plus courte est de 3.

Cependant, on constate qu'il existe un chemin 1-3-2 dont le coût est de seulement 2. Or, l'algorithme de Dijkstra indique que la distance la plus courte entre le nœud « 1 » et le nœud « 2 » est de 5. Par conséquent, Dijkstra n'a pas calculé correctement la distance la plus courte. Ceci s'explique par le fait que Dijkstra est un algorithme glouton. Ainsi, une fois qu'un nœud est marqué comme visité, il n'est plus considéré, même s'il existe un chemin plus court. Ce problème survient uniquement lorsque les arêtes ont un coût ou un poids négatif.

Dans ce cas précis, l'algorithme de Dijkstra ne parvient pas à calculer le chemin le plus court entre deux nœuds. Il présente donc certaines limitations. Pour résoudre ce problème d'arêtes négatives, on utilise un autre algorithme, appelé « algorithme de Bellman-Ford », capable de traiter les arêtes négatives.

Complexité de l'algorithme de Dijkstra

L'implémentation ci-dessus utilisait deux boucles « for ». Ces boucles s'exécutent pour le nombre de sommets. La complexité temporelle est donc O(V²)Ici, le terme « O » est une notation qui donne une hypothèse pour l'algorithme de Dijkstra.

On peut stocker le graphe à l'aide d'une file de priorité. Une file de priorité est une structure de données de type tas binaire. Elle sera plus efficace qu'une matrice 2D. Une arête de coût minimal aura une priorité élevée. La complexité temporelle sera alors de O(n log n). O(E log V). Ici, E est le nombre d’arêtes et V est le nombre de sommets.

La complexité de l'espace est O(V²), car nous utilisons une matrice de contiguïté (tableau 2D). La complexité de l'espace peut être optimisée à l'aide d'une liste de contiguïté ou d'une structure de données de file d'attente.

FAQ