Longueur du plus court chemin avec BFS
Comme l’algorithme BFS part d’un nœud spécifique et s’étend progressivement à ses voisins, il est possible de trouver la distance la plus courte entre le nœud de départ et tous les autres nœuds du graphe. Pour cela, il suffit de modifier légèrement l’algorithme initial. Nous utiliserons un tableau de distances
d, dans lequel toutes les valeurs seront initialisées à -1. Si la valeur d’un sommet est -1, cela signifie que ce sommet n’a pas encore été visité. Si la valeur est positive, elle indique la distance entre ce sommet et le point de départ :from collections import deque
n, e = map(int, input().split()) # n : sommets, e : arêtes
g = [[] for _ in range(n)] # graph - liste d'adjacence
for _ in range(e): # lecture des arêtes
a, b = map(int, input().split()) # a -> b and b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # sommet de départ
d = [-1] * n # distance depuis le sommet de départ
q = deque([start]) # file de sommets
d[start] = 0 # la distance du sommet de départ à lui-même est de 0
while q: # tant que la file n'est pas vide
v = q.popleft() # récupère le sommet de la file
print(v, end=' ') # affiche 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
q.append(to) # ajoute le sommet à la file
print(d)Nous commençons par initialiser le tableau de distance
d avec -1, pour indiquer que les sommets ne sont pas encore utilisés. Ensuite, la valeur de d[start] est mise à 0, ce qui signifie que la distance du sommet de départ à lui-même est 0.Au fur et à mesure que l’algorithme traite d’autres nœuds, leurs valeurs associées sont mises à jour dans le tableau de distances
d, ce qui nous permet de connaître la distance de chaque nœud par rapport au nœud de départ.Examinons quelques exemples concrets :
n = 4, e = 4
Les paires d’entrées
a, b sont : [(0, 1), (0, 2), (1, 2), (3, 2)]Le sommet de départ est 3
d = [-1, -1, -1, 0],q = [3]
v = 3,q = []→ on ajoute tous les voisins non visités à la file
d = [-1, -1, 1, 0],q = [2]
v = 2,q = []→ on ajoute tous les voisins non visités à la file
d = [2, 2, 1, 0],q = [0, 1]
v = 0,q = [1]→ on ajoute tous les voisins non visités à la file
v = 1,q = []→ on ajoute tous les voisins non visités à la file
- Terminé
n = 5, e = 4
Les paires d’entrées
a, b sont : [(0, 1), (0, 2), (1, 2), (3, 4)]Le sommet de départ est 0
d = [0, -1, -1, -1, -1],q = [0]
v = 0,q = []→ on ajoute tous les voisins non visités à la file
d = [0, 1, 1, -1, -1],q = [1, 2]
v = 1,q = [2]→ on ajoute tous les voisins non visités à la file
v = 2,q = []→ on ajoute tous les voisins non visités à la file
- Terminé
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Défi : Trouver la longueur du plus court chemin
Étant donné un graphe non orienté avec
v sommets et e arêtes, vous devez calculer la distance la plus courte entre le sommet 1 et le sommet v. Si ces sommets ne sont pas connectés, le programme devra imprimer Impossible.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 100 000) et e (1 ≤ e ≤ 100 000).Les
e lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v) indiquant que le sommet v1 est connecté au sommet v2, et réciproquement.Sortie
Le programme doit afficher la longueur du plus court chemin entre
1 et v.Exemples
Entrée | Sortie |
5 6
1 2
2 3
1 3
3 4
4 3
3 5 | 2 |
2 1
1 2 | 1 |
2 0 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB