REPUBLIQUE DEMOCRATIQUE DU CONGO
MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET
UNIVERSITAIRE
UNIVERSITE PROTESTANTE AU CONGO
FACULTE DES SCIENCES INFORMATQUES
B.P 4745 KINSHASA II
TRAVAIL PRATIQUE DE RECHERCHE
OPÉRATIONNELLE POUR INFORMATICIEN
Algorithme de Dijkstra
Par
FIMPA MALANGU Rilord
Professeur : Israël DISASHI
Janvier 2026
Problème
André et Jacqueline veulent connaitre l’itinéraire la plus rapide pour atteindre l’Afrique du Sud
en partant de la RDC,
Le tableau ci-dessous reprend la durée des trajets entre chaque pays
Pays A Pays B Durée du trajet (en avion)
RDC Angola [1h 40 min, 3h 18 min]
Angola Namibie [3h 38 min, 8h 30 min]
Namibie Botswana [1h 30 min, 2h 30 min]
Botswana Afrique du Sud [1h 28 min, 1h 30 min]
Angola Zambie [10h 40 min, 11h]
Zambie Zimbabwe [3h , 8h]
Zimbabwe Afrique du Sud [1h 45 min, 2h]
RDC Zambie [1h 3 min, 1h 7 min]
Angola Zambie [23h 12 min, 24h]
Namibie Angola [2h 30 min, 4h]
Namibie Zambie [6h 30 min, 9h 16 min]
Namibie Afrique du Sud [1h 45 min, 3h 30 min]
Botswana Zimbabwe [3h, 4h]
Zambie Botswana [1h 30 min, 2h]
Zimbabwe Namibie [2h 26 min, 6h 16 min]
Algorithme de Dijkstra
Nous avons choisi d’implémenter l’algorithme de Dijkstra en Python afin de trouver le plus
court chemin menant à l’Afrique du Sud
Voici, ci-dessus, le graphe correspondant à la situation.
La Bibliothèque heapq est fournie par Python pour travailler avec les files d’attente prioritaires.
De cette bibliothèque nous importons les fonctions
• heapify : transforme une liste de tuples avec des paires priorité-valeur en une file
d’attente prioritaire ;
• heappush : ajoute un élément à la file d’attente avec la priorité qui lui est associée ;
• heappop : Supprime et renvoie l’élément ayant la plus haute priorité.
Nous avons créé une classe Graph pour représenter les graphes, elle utilisera une liste
d’adjacence dictionnaire qui contient des paires nœud-valeur. Ce dictionnaire est mis à jour
chaque fois que nous visitons un nœud et ses voisins. Les valeurs initiales de tous les nœuds
sont fixées à l’infini, tandis que la valeur de la source est de 0. Le dictionnaire predecessors
contient le parent immédiat de chaque nœud impliqué dans le chemin le plus court vers la
source.
Nous créons une nouvelle file d’attente prioritaire qui ne contient initialement que le nœud
source. La priorité de chaque élément à l’intérieur de pq sera sa valeur actuelle. Nous initialisons
un ensemble vide pour enregistrer les nœuds visités.
Nous parcourons les nœuds non visités à l’aide d’une boucle while. Tant que la file d’attente
des priorités n’est pas vide, nous continuons d’extraire le nœud le plus prioritaire (avec la valeur
minimale) et d’extraire sa valeur et son nom vers current_distance et current_node. Si le site
current_node se trouve à l’intérieur du site visited, nous l’ignorons. Dans le cas contraire, nous
le marquons comme visité, puis nous passons à la visite de ses voisins.
Pour chaque voisin, nous calculons la distance provisoire par rapport au nœud actuel en ajoutant
la valeur actuelle du voisin au poids de l’arête de connexion. Ensuite, nous vérifions si la
distance est inférieure à la distance du voisin dans distances. Si c’est le cas, nous mettons à jour
le dictionnaire distances et ajoutons le voisin avec sa distance provisoire à la file d’attente
prioritaire.
En utilisant la fonction shortest_distances, nous générons le dictionnaire predecessors. Ensuite,
nous lançons une boucle while qui revient en arrière d’un nœud à partir du nœud actuel à chaque
itération jusqu’à ce que le nœud source soit atteint. Ensuite, nous renvoyons la liste inversée
qui contient le chemin de la source à la cible.
On instancie un objet de notre classe Graph qui va prendre en argument le graphe que nous
avons défini plus tôt et nous appelons la méthode shortest_path sur notre objet afin de connaitre
le chemin le plus court entre la RDC et l’Afrique du Sud.
Résultat