L’Algorithme
Recommandation
Si vous n’êtes pas encore familier avec les algorithmes de chemin le plus court, vous devriez commencer par un algorithme un peu plus simple comme l’algorithme de Bellman-Ford. Vous pouvez trouver une explication de l’algorithme de Bellman-Ford ici.
def dijkstra(G: Graph, p:function(int,int) -> int, source: int) -> [prev: List[int], weight: List[int]]:
'''Pseudo-code de Dijkstra.
Args:
G : Graph : Un graphe sans cycles négatifs
p : function(int, int) -> int : Une fonction qui retourne le poids de l'arête (u, v) en O(1). Exemple p(1,2) donne le poids de l'arête (1,2)
source : int : L'indice du sommet source dans V
Returns:
prev : List[int] : Un tableau contenant le sommet prédécesseur de chaque sommet.
weight : List[int] : Un tableau contenant, pour chaque sommet, le poids du chemin le plus court (somme des poids) de la source à ce sommet.
'''
# Initialisation
for v in G.vertices:
weight[v] = inf
prev[v] = '-'
weight[source] = 0 # De la source à la source, le poids est 0
Q = G.vertices # Tous les sommets
while Q != {}: # Tant que Q n'est pas vide
temp = inf
minQ = -1
for q in Q:
if weight[q] < temp:
temp = weight[q]
minQ = q
Q.remove(minQ)
for q_prime in G.successors(minQ):
if weight[q_prime] > weight[minQ] + p(minQ, q_prime):
weight[q_prime] = weight[minQ] + p(minQ, q_prime)
prev[q_prime] = minQ
return prev, weight
Dijkstra choisirait le chemin de A à C de poids 1 puisque le poids de B est 4. Mais le chemin le plus court est de A à B à C de poids -1.
Exemple
Voici 2 digraphes (graphes orientés).
- Pouvez-vous utiliser l’algorithme de Dijkstra sur ces graphes pour trouver le chemin le plus court de s à t ?
- Si oui, déterminez le chemin le plus court de s à t en utilisant l’algorithme de Dijkstra.
Exemple 1
Je m’excuse pour les arêtes qui se croisent, le placement est automatique.
Solution 1
Une arête dans le graphe est associée à un poids négatif. Par conséquent, l’algorithme de Dijkstra ne s’applique pas ici. Vous devriez utiliser l’algorithme de Bellman-Ford (ou un autre).
Exemple 2
Solution 2
Vous pouvez combiner les 2 tableaux si vous préférez, par exemple en mettant dans chaque cellule “poids/préd”.
Tableau des Poids
| Étapes | s | 0 | 1 | 2 | 3 | 4 | 5 | t |
|---|---|---|---|---|---|---|---|---|
| Init | 0 | |||||||
| Q -= s | / | 6 | 4 | 2 | ||||
| Q -= 3 | / | 6 | 4 | / | ||||
| Q -= 1 | / | 6 | / | / | 6 | |||
| Q -= 0 | / | / | / | 9 | / | 6 | ||
| Q -= 4 | / | / | / | 9 | / | / | 7 | |
| Q -= 5 | / | / | / | 8 | / | / | / | |
| Q -= 2 | / | / | / | / | / | / | / | 11 |
| Q -= t | / | / | / | / | / | / | / | / |
Quelques indices pour comprendre ce tableau :
- Initialisation : D’abord, nous savons seulement que le sommet source est à une distance de 0 de lui-même. Le reste est inconnu, donc nous mettons
. - Étapes suivantes : À partir des sommets connus (ici seulement la source), nous regardons les successeurs du sommet avec le plus petit poids. Nous définissons la distance au successeur si elle est inférieure à la valeur enregistrée. N’oubliez pas de mettre à jour le tableau des prédécesseurs en même temps.
- Q -= : Nous retirons le sommet avec le plus petit poids de Q. Ici, pour cette étape, nous retirons le sommet s.
- Astuce pour la lisibilité : Si le sommet n’est plus dans Q, nous mettons un ”/” dans la cellule. Le nombre au-dessus est le vrai poids du sommet.
- Fin de l’algorithme : Lorsque Q est vide, nous pouvons enfin lire le dernier poids de
.
Tableau des Prédécesseurs
| Étapes | s | 0 | 1 | 2 | 3 | 4 | 5 | t |
|---|---|---|---|---|---|---|---|---|
| Init | - | - | - | - | - | - | - | - |
| Q -= s | / | s | s | - | s | - | - | - |
| Q -= 3 | / | s | s | - | / | - | - | - |
| Q -= 1 | / | s | / | - | / | 1 | - | - |
| Q -= 0 | / | / | / | 0 | / | 1 | - | - |
| Q -= 4 | / | / | / | 0 | / | / | 4 | - |
| Q -= 5 | / | / | / | 5 | / | / | / | - |
| Q -= 2 | / | / | / | / | / | / | / | 2 |
| Q -= t | / | / | / | / | / | / | / | / |
Trouvons le chemin le plus court de s à t :
- Le prédécesseur de t est 2
- Le prédécesseur de 2 est 5
- Le prédécesseur de 5 est 4
- Le prédécesseur de 4 est 1
- Le prédécesseur de 1 est s
Le chemin le plus court de s à t est donc :
Le poids total est :