Reconstruire le chemin le plus court
Lorsque l’on calcule le chemin le plus court dans un graphe, il est également possible de le reconstruire à la fin.
Pour cela, on peut stocker, pour chaque sommet visité, le sommet « parent ». Autrement dit, si l’on ajoute le sommet
to dans la file après avoir traité le sommet v, on peut indiquer que le sommet parent de to est v. Cela permettra de reconstruire tout le chemin à la fin. On commencera alors par le dernier nœud du chemin pour remonter à son parent, puis au parent de ce nœud, et ainsi de suite jusqu’à atteindre un nœud qui n’a pas de parent, à savoir le sommet de départ. Cette approche peut s’implémenter en stockant un tableau de parents supplémentaire, p:start = int(input()) # sommet de départ
d = [-1] * n # distance depuis le sommet de départ
p = [-1] * n # sommet parent
q = deque([start]) # file de sommets
d[start] = 0 # distance du sommet de départ à lui-même est 0
while q: # tant que la file n'est pas vide
v = q.popleft() # extraire un sommet de la file
print(v, end=' ') # afficher le sommet
for to in g[v]: # pour chaque sommet connecté à v
if d[to] == -1: # si le sommet n'a pas été visité
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
p[to] = v # le parent du sommet to est v
q.append(to) # ajouter le sommet à la file
# Reconstruction du chemin depuis le sommet de départ jusqu’au sommet d’arrivée
end = int(input()) # sommet d'arrivée
path = [] # chemin du sommet de départ au sommet d'arrivée
while end != -1: # tant qu'il existe un sommet parent
path.append(end) # ajouter le sommet au chemin
end = p[end] # passer au sommet parent
print(*path[::-1], sep=' -> ') # afficher le chemin dans l'ordre inverseAinsi, après avoir ajouté chaque sommet dans la file, nous enregistrons son parent dans le tableau
p puis nous reconstruisons le chemin à la toute fin, en partant du dernier nœud jusqu’au premier. Au final, le chemin doit être affiché à l’envers, puisque nous ajoutons les nœuds à partir de la fin et examinons leurs parents un par un, jusqu’à arriver au sommet de départ. Par conséquent, pour passer du départ à l’arrivée, il est nécessaire d’inverser ce chemin.Simulons cet algorithme sur plusieurs jeux de données :
n = 4, e = 4
Les paires d’entrée
a, b sont les suivantes : [(0, 1), (0, 2), (1, 2), (3, 2)]Le sommet de départ est 3 et le sommet d’arrivée est 0
p = [-1, -1, -1, -1],q = [3]
v = 3,q = []→ ajouter tous les voisins qui ne sont pas encore utilisés dans la file
p = [-1, -1, 3, -1],q = [2]
v = 2,q = []→ ajouter tous les voisins qui ne sont pas encore utilisés dans la file
p = [2, 2, 3, -1],q = [0, 1]
v = 0,q = [1]→ ajouter tous les voisins qui ne sont pas encore utilisés dans la file
v = 1,q = []→ ajouter tous les voisins qui ne sont pas encore utilisés dans la file
- Reconstruire le chemin
end = 0→end = 2→end = 3
- impression de
3 → 2 → 0
Remarquez que si la valeur de
d[end] vaut toujours -1 à la fin de l’algorithme, cela signifie qu’il était impossible d’atteindre le sommet d’arrivée.Défi : Trouver l’itinéraire le plus court
L’Internet est un ensemble d’ordinateurs interconnectés capables de transférer des données. Dans notre cas, ces ordinateurs sont numérotés de 1 à
n, et nous connaissons les ordinateurs qui sont reliés entre eux. Alice souhaite envoyer un message à Bob aussi rapidement que possible, ce qui implique que l’itinéraire doit être le plus court possible.Alice dispose d’un ordinateur numéroté
a, tandis que l’ordinateur de Bob porte le numéro b. Votre tâche consiste à trouver un itinéraire optimal de machines permettant de transmettre le message d’Alice à Bob le plus vite possible.Entrée
La première ligne de l’entrée contient deux entiers
n (1 ≤ n ≤ 100 000) et e (1 ≤ e ≤ 100 000), représentant respectivement le nombre d’ordinateurs et le nombre de connexions dans le réseau.La ligne suivante contient deux nombres
a et b (1 ≤ a, b ≤ n).Les
e lignes suivantes comportent chacune une paire d’entiers c1, c2 (1 ≤ c1, c2 ≤ n), indiquant que l’ordinateur c1 est connecté à l’ordinateur c2 et inversement.Sortie
Le programme doit afficher l’itinéraire le plus optimal pour le message, en séparant chaque numéro d’ordinateur par un espace. S’il existe plusieurs itinéraires optimaux, le programme peut en imprimer n’importe lequel.
Exemples
Input | Entrée |
5 5
1 5
1 2
2 3
1 3
3 4
3 5 | 1 3 5 |
5 6
1 5
1 2
2 3
2 4
3 4
4 5
3 5 | 1 2 4 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB