Network Delay Time
Un réseau comporte n nœuds étiquetés de 1 à n. Le lien times[i] = [u, v, w] transporte un signal du nœud u au nœud v en w unités de temps, uniquement dans cette direction.
Un signal quitte le nœud k à l’instant 0 et se propage le long de chaque lien qu’il peut emprunter. Renvoyez le temps auquel le dernier nœud le reçoit, ou -1 si un nœud ne le reçoit jamais.
Fonction
- timesinteger-2d-array
- les liens orientés, chacun sous la forme [u, v, w]
- ninteger
- le nombre de nœuds
- kinteger
- le nœud qui envoie le signal
- Renvoieinteger
- le moment où le dernier nœud reçoit le signal, ou -1
Contraintes
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ netu ≠ v0 ≤ w ≤ 100- Aucun couple de liens ne possède à la fois le même
uet le mêmev. 1 ≤ k ≤ n
Exemples
- Entrée
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- Sortie
- 4
- Explication
- Le lien direct atteint le nœud 2 au temps 4, mais l’itinéraire passant par le nœud 3 arrive à 1 + 2 = 3. Le nœud 4 reçoit le signal en dernier, à 3 + 1 = 4.
- Entrée
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Sortie
- -1
- Explication
- Le nœud 2 reçoit le signal à l’instant 3, mais le seul lien relié au nœud 3 va de 3 à 1. Le nœud 3 ne le reçoit jamais, donc la réponse est -1.
- Entrée
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Sortie
- 2
- Explication
- Le lien vers le nœud 3 prend 0, donc le nœud 3 reçoit le signal au temps 0. Le nœud 1 le reçoit ensuite à 0 + 2 = 2, plus tôt qu’avec son lien direct qui prend 5.
Pour aller plus loin
Supposons que le signal s’atténue après avoir traversé m liens. Comment trouver le temps auquel le dernier nœud l’entend dans cette limite ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Un nœud reçoit le signal au bout du temps correspondant au trajet le plus rapide pour l’atteindre depuis
k. La réponse est donc le plus grand de ces temps les plus rapides, ou -1 lorsqu’un nœud n’a aucun trajet.Aucun lien ne prend un temps négatif. Ainsi, parmi les nœuds dont le temps n’est pas encore définitif, celui qui a le plus petit temps provisoire ne peut pas être atteint plus rapidement : tout autre chemin vers lui passe par un autre de ces nœuds, qui n’est pas atteint plus tôt. Validez les nœuds dans l’ordre d’arrivée.
Gardez un tas min de paires
(time, node). Retirez le plus petit élément, ignorez-le si le nœud a déjà un temps plus petit, et ajoutez chaque voisin dont le temps s'améliore. Lorsque le tas est vide, prenez le temps le plus grand.
Solution
Chaque nœud reçoit le signal après un délai égal à la longueur de son trajet le plus rapide depuis k : il s’agit donc de calculer les plus courts chemins depuis une source unique, puis de prendre le maximum, ou de renvoyer -1 si un nœud n’a aucun chemin. Les durées des liaisons ne sont jamais négatives, donc l’algorithme de Dijkstra traite chaque nœud une seule fois. Ci-dessous, E correspond à times.length.
Recherche en profondeur qui revisite chaque fois qu’un itinéraire plus rapide est trouvé
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Parcours depuis k en profondeur, en conservant le temps écoulé et en enregistrant le temps d’arrivée le plus rapide pour chaque nœud. Un itinéraire qui atteint un nœud à un moment égal ou postérieur à celui enregistré s’arrête ; un itinéraire plus rapide met à jour l’enregistrement et poursuit la recherche. Chaque enregistrement finit par correspondre au temps réellement le plus rapide, car l’itinéraire le plus rapide l’améliore à un moment donné.
Un nœud peut être amélioré de nombreuses fois. Disposez 18 portes en ligne, chaque paire étant reliée par un lien gratuit et par un détour de 65,536, 32,768, puis ainsi de suite jusqu’à 1. En essayant d’abord les détours, la recherche atteint la dernière porte à 131,072 moments différents et parcourt tout ce qui se trouve derrière à chaque fois : le travail est exponentiel en n.
Algorithme
- Initialisez chaque meilleur temps à l’infini et empilez
(k, 0). - Dépilez
(node, t). Ignorez-le sauf sit < best[node]; définissez alorsbest[node] = t. - Empilez
(next, t + w)pour chaque lien partant denodedont l’heure d’arrivée est meilleure quebest[next]. - Lorsque la pile est vide, renvoyez -1 si un meilleur temps est infini, sinon le plus grand.
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
best = [INF] * (n + 1) # the fastest arrival found so far at each node
stack = [(k, 0)]
while stack:
node, t = stack.pop()
# A route that is not faster than one already found adds nothing.
if t >= best[node]:
continue
best[node] = t
# Push in reverse so the first listed edge is explored first.
for nxt, w in reversed(graph[node]):
if t + w < best[nxt]:
stack.append((nxt, t + w))
worst = 0
for node in range(1, n + 1):
if best[node] == INF:
return -1
worst = max(worst, best[node])
return worstBellman-Ford : relâcher chaque arête jusqu’à n-1 fois
Intuition
Conservez un temps provisoire dist pour chaque nœud, 0 pour k. Relâcher un lien u → v abaisse dist[v] à dist[u] + w si cette valeur est plus petite. Bellman-Ford relâche chaque lien à chaque passe.
Prenez le chemin le plus rapide vers un nœud, par exemple k → a → b → v. La première passe rend dist[a] définitif, la deuxième dist[b], la troisième dist[v]. Un chemin le plus rapide ne repasse jamais par un même nœud : il comporte donc au plus n-1 liens, et n-1 passes suffisent à fixer les valeurs de tous les nœuds.
Chaque passe coûte O(E). Une chaîne de 3 000 nœuds répertoriée en partant de son extrémité la plus éloignée nécessite 2 999 passes sur 4 000 liens, soit environ 12 millions de relâchements.
Algorithme
- Définis
dist[k] = 0et chaque autredistà l’infini. - Répète jusqu’à n-1 fois : pour chaque lien
[u, v, w], sidist[u] + w < dist[v], définisdist[v] = dist[u] + w. - Arrête-toi plus tôt après une passe qui ne change rien.
- Retourne -1 si un
distest encore infini, sinon le plus grand.
def networkDelayTime(times, n, k):
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
# A fastest route visits each node at most once, so it has at most n-1 edges,
# and n-1 passes over every edge are enough to find it.
for _ in range(n - 1):
changed = False
for u, v, w in times:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed: # a pass that improves nothing means every time is final
break
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worstAlgorithme de Dijkstra avec un tas min
Intuition
Parmi les nœuds qui ne sont pas encore réglés, celui dont le temps provisoire est le plus faible est déjà définitif. Tout autre itinéraire vers ce nœud doit quitter les nœuds réglés en passant par un nœud non réglé dont le temps est au moins aussi grand, et les liens suivants ne font qu’ajouter du temps, puisqu’aucun n’est négatif. On règle donc ce nœud, on relâche ses liens une fois, puis on recommence.
Un tas min permet de trouver le temps le plus faible. Lorsqu’un nœud est amélioré, ajoutez une nouvelle entrée et laissez l’ancienne en place ; une entrée retirée dont le temps dépasse dist est périmée, vous pouvez donc l’ignorer. Chaque lien ajoute au plus une entrée, le tas contient donc au plus E + 1 entrées et le coût total est O(E log E).
Algorithme
- Définissez
dist[k] = 0, toutes les autres valeurs dedistà l’infini, puis ajoutez(0, k)à un tas min. - Retirez le plus petit
(t, node); sit > dist[node], ignorez-le car il est obsolète. - Pour chaque liaison
node → nextde duréew, sit + w < dist[next], définissezdist[next] = t + wet ajoutez(t + w, next)au tas. - Quand le tas est vide, renvoyez -1 si une valeur de
distest infinie ; sinon, renvoyez la plus grande.
import heapq
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
heap = [(0, k)] # (arrival time, node), smallest time on top
while heap:
t, node = heapq.heappop(heap)
# A stale entry: this node was already reached sooner.
if t > dist[node]:
continue
# t is now final: every other route reaches node later.
for nxt, w in graph[node]:
if t + w < dist[nxt]:
dist[nxt] = t + w
heapq.heappush(heap, (t + w, nxt))
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worst
Pièges et cas limites
- Considérer les liens comme bidirectionnels.
[3, 1, 2]transmet le signal de 3 à 1 uniquement ; le nœud 3 ne le reçoit donc jamais dans le deuxième exemple. - Utiliser un simple parcours en largeur. Il trouve le chemin comportant le moins de liens : dans le premier exemple, il donne au nœud 2 un temps de 4 au lieu de 3.
- Oublier le -1. Prendre le maximum sans vérification renvoie l’infini ou masque le nœud qui n’a jamais reçu le signal.
- Utiliser le plus grand entier comme infini.
dist[u] + wdéborde alors et devient un nombre négatif pour ununon atteint ; ignorez les nœuds non atteints ou utilisez 10^9.
Questions fréquentes3
Quelle est la complexité temporelle de Network Delay Time ?
Avec l’algorithme de Dijkstra et un tas binaire, la complexité est de O(E log E), où E est le nombre de liens. Cela équivaut à O(E log n), puisque E est au plus égal à n². L’espace nécessaire est de O(n + E). Bellman-Ford prend un temps de O(n · E).
Pourquoi l’algorithme de Dijkstra a-t-il besoin de poids non négatifs ?
Dijkstra ne revisite jamais un nœud dont le traitement est terminé, ce qui n’est sûr que si aucun itinéraire ultérieur ne peut être plus court. Avec les liens A → B de durée 2, A → C de durée 3 et C → B de durée -2, il fixe la distance de B à 2, alors que l’itinéraire passant par C l’atteint en 1. Bellman-Ford gère les durées négatives.
Peux-tu résoudre le problème du délai réseau sans tas ?
Oui. Dijkstra avec un tableau simple parcourt tous les nœuds non fixés pour trouver le temps le plus court, ce qui coûte O(n²) au total. Il est plus performant sur les graphes denses, où E est proche de n². Sur les graphes clairsemés, par exemple avec 3 000 nœuds et 4 000 liens, la version avec tas effectue beaucoup moins de travail.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def networkDelayTime(times, n, k):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Résultat attendu
4