Network Delay Time

Q: 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. C’est équivalent à O(E log n), puisque E est au plus égal à n². La liste d’adjacence, les temps et le tas nécessitent O(n + E) espace. L’algorithme de Bellman-Ford prend O(n · E) temps et O(n) espace.

Q: Pourquoi l’algorithme de Dijkstra a-t-il besoin de poids non négatifs ?

Dijkstra fixe le nœud dont le temps provisoire est le plus petit et ne l’examine plus jamais. Cela n’est sûr que si aucun itinéraire ultérieur ne peut être plus court et, avec des poids non négatifs, chaque itinéraire passant par un nœud non fixé coûte au moins autant que le temps de ce nœud. Un lien négatif invalide ce raisonnement : un itinéraire passant par un nœud qui semblait plus coûteux peut finalement être moins cher. Pour les poids négatifs, utilisez Bellman-Ford.

Q: Pourquoi ne pas utiliser BFS pour le délai de propagation du réseau ?

BFS visite les nœuds en fonction du nombre de liens qui les séparent du départ, ce qui correspond à l’ordre d’arrivée uniquement lorsque chaque lien prend le même temps. Ici, les durées des liens diffèrent, donc un itinéraire comportant plus de liens peut arriver plus tôt. Si toutes les durées étaient égales, BFS suffirait, et avec des durées de 0 et 1 seulement, un 0-1 BFS basé sur une deque fonctionne.

Q: Peux-tu résoudre le problème du délai de transmission sur le réseau sans tas ?

Oui. Dijkstra avec un tableau simple parcourt tous les nœuds non réglés pour trouver le temps le plus court, ce qui coûte O(n²) au total et ne nécessite pas de tas. C’est le meilleur choix pour les graphes denses, où E est proche de n². Pour les graphes clairsemés, comme les grands tests ici avec 3,000 nœuds et 4,000 liens, la version avec tas effectue beaucoup moins de travail.

MoyenPlus courts chemins Graphes Tas

+10

Un réseau comporte n nœuds, numérotés de 1 à n. Vous obtenez ses liaisons sous la forme d’une liste times, où times[i] = [u, v, w] signifie qu’un signal envoyé depuis le nœud u atteint le nœud v après w unités de temps. Les liaisons ne fonctionnent que dans un seul sens.

Un signal part du nœud k au temps 0 et se propage le long de toutes les liaisons 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

networkDelayTime(times: integer-2d-array, n: integer, k: integer) → integer

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 ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n et u ≠ v
0 ≤ w ≤ 100
Aucun lien ne partage à la fois le même u et le même v.
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 nœud 3 reçoit le signal au temps 1. Le nœud 2 pourrait le recevoir au temps 4 via sa liaison directe, mais le trajet passant par le nœud 3 arrive à 1 + 2 = 3, et le nœud 4 le reçoit à 3 + 1 = 4. Le nœud 4 est le dernier, au temps 4.

+16 tests cachés à la soumission

Pour aller plus loin

Supposons que le signal s’atténue après avoir traversé m liens. Comment trouver le moment où le dernier nœud l’entend dans cette limite ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque nœud reçoit le signal au bout du temps correspondant à la durée de son trajet le plus rapide depuis k : il s’agit donc de trouver les plus courts chemins à source unique dans un graphe orienté, puis de prendre le maximum. La réponse est le plus grand des temps de trajet les plus courts, ou -1 si un nœud n’est pas accessible. Les durées des liens ne sont jamais négatives, ce qui permet à l’algorithme de Dijkstra de valider chaque nœud une seule fois, dans l’ordre d’arrivée, à l’aide d’un tas min. Ci-dessous, E correspond au nombre de liens, 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

Commencez une recherche au nœud k avec un temps de 0 et suivez chaque lien en cumulant le temps écoulé. Pour chaque nœud, enregistrez le temps d’arrivée le plus rapide observé. Lorsque la recherche atteint un nœud à un temps égal ou supérieur à celui enregistré, arrêtez-vous là : tout ce que cette route pourrait apporter plus loin a déjà été apporté par la route plus rapide. Lorsqu’elle atteint le nœud plus tôt, la valeur enregistrée est améliorée, et tout ce qui se trouve après le nœud pourrait également être amélioré ; la recherche se poursuit donc à partir de celui-ci.

Cela fonctionne toujours. La recherche ne s’arrête que lorsqu’aucune route n’améliore aucune valeur enregistrée, et la route la plus rapide vers chaque nœud améliore la valeur enregistrée de ce nœud à un moment donné ; chaque valeur enregistrée finit donc par correspondre au véritable temps le plus rapide.

Le problème, c’est le nombre de fois où un nœud peut être amélioré. Une recherche en profondeur suit le premier lien rencontré jusqu’au bout ; elle peut donc atteindre un nœud par une route lente, puis par une route légèrement plus rapide, puis par une autre encore plus rapide, et parcourir à chaque fois tout ce qui se trouve après le nœud. Imaginez 18 barrières alignées. Entre chaque paire de barrières, vous pouvez emprunter un lien gratuit ou un détour, une chaîne de liens dont les durées totalisent 65,536, 32,768, et ainsi de suite jusqu’à 1. En essayant d’abord les détours, la recherche atteint la dernière barrière à 131,072 moments différents, chacun plus tôt que le précédent, et parcourt à chaque fois les 1,700 nœuds qui se trouvent après elle : environ 220 millions d’étapes. Deux des grands tests sont construits de cette façon, l’un avec chaque détour indiqué avant son lien gratuit et l’autre avec le détour indiqué après, de sorte qu’une recherche se heurte à l’un d’eux, quel que soit l’ordre dans lequel elle essaie les liens.

Algorithme

Construis une liste d’adjacence : pour chaque nœud, les liens qui en partent et leurs durées.
Définis le meilleur temps de chaque nœud comme étant l’infini et empile (k, 0).
Dépile (node, t). Si t n’est pas inférieur à best[node], ignore-le ; sinon, définis best[node] = t.
Empile (next, t + w) pour chaque lien partant de node dont l’heure d’arrivée est meilleure que best[next].
Lorsque la pile est vide, renvoie -1 si un meilleur temps est encore infini ; sinon, renvoie 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 worst

Bellman-Ford : relâcher chaque arête jusqu’à n-1 fois

Intuition

Conservez un temps provisoire dist pour chaque nœud : 0 pour k, l’infini pour les autres. Relâcher un lien u → v de temps w signifie : si dist[u] + w est inférieur à dist[v], le lien offre un chemin plus rapide vers v, alors diminuez dist[v] pour le ramener à cette valeur. Bellman-Ford effectue des passages sur toute la liste et relâche chaque lien à chaque passage.

Pourquoi cela donne-t-il les bons temps à la fin ? Prenons le chemin le plus rapide vers un nœud, disons k → a → b → v. Le premier passage relâche k → a alors que dist[k] vaut déjà 0, donc à la fin de ce passage, dist[a] est définitif. Le deuxième passage rend dist[b] définitif, le troisième, dist[v]. Un chemin le plus rapide n’a jamais besoin de passer deux fois par un même nœud, puisqu’une boucle ne prend jamais un temps négatif : il comporte donc au plus n-1 liens, et n-1 passages suffisent à fixer la valeur de chaque nœud. Un passage qui ne change rien prouve qu’aucun passage ultérieur ne pourra le faire : vous pouvez donc vous arrêter là.

Chaque passage coûte O(E), donc le pire cas est O(n · E). L’ordre de la liste détermine l’ampleur du problème : si les liens d’un long chemin sont listés en partant de son extrémité la plus éloignée vers le début, chaque passage fixe la valeur d’un nœud supplémentaire. Un grand test correspond exactement à ce cas : une chaîne de 3,000 nœuds listée à l’envers, qui nécessite 2,999 passages sur 4,000 liens, soit environ 12 millions de relâchements. Cela s’exécute tout de même assez rapidement avec cette taille, mais le travail augmente en fonction de n fois E. La force de Bellman-Ford réside ailleurs : il reste correct lorsque certains temps de lien sont négatifs, contrairement à Dijkstra.

Algorithme

Définis dist[k] = 0 et toutes les autres valeurs de dist à l’infini.
Répète jusqu’à n-1 fois : pour chaque lien [u, v, w], si dist[u] + w < dist[v], définis dist[v] = dist[u] + w.
Arrête-toi après un passage qui ne change rien.
Renvoie -1 si une valeur de dist est toujours infinie, sinon renvoie la plus grande.

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 worst

L’algorithme de Dijkstra avec un tas min

Intuition

Bellman-Ford effectue des passes inutiles, car il relâche les liens sortant de nœuds dont les temps ne sont pas encore définitifs, et doit y revenir. L’algorithme de Dijkstra relâche les liens de chaque nœud exactement une fois, au moment où son temps devient définitif. La question est de savoir comment le déterminer.

La réponse est une règle gloutonne : parmi les nœuds qui ne sont pas encore fixés, celui dont le temps provisoire est le plus petit est déjà définitif. Tout autre itinéraire pour y parvenir doit quitter les nœuds fixés à un moment donné, en passant par un nœud non fixé dont le temps est au moins aussi grand, et les liens qui suivent ne peuvent qu’ajouter du temps, puisqu’aucun n’est négatif. Tu fixes donc ce nœud, relâches ses liens et recommences. Dans le premier exemple, le nœud 1 est fixé à 0 et propose au nœud 2 le temps 4 et au nœud 3 le temps 1. Le nœud 3 est le plus proche, il est fixé à 1 et ramène le temps du nœud 2 à 3. Le nœud 2 est fixé à 3 et propose au nœud 4 le temps 4, qui est fixé en dernier. La réponse est 4.

Un tas min permet de trouver rapidement le plus petit temps provisoire. Ajoute (time, node) chaque fois que le temps d’un nœud s’améliore, et laisse l’ancienne entrée dans le tas au lieu de la rechercher. Lorsque cette ancienne entrée ressort plus tard, son temps est supérieur au temps actuel du nœud, donc tu l’ignores. Chaque lien ajoute au plus une entrée, le tas ne contient donc jamais plus de E + 1 entrées, et chaque ajout ou retrait coûte O(log E). Cela donne un coût total de O(E log E), avec un espace de O(n + E) pour la liste d’adjacence, les temps et le tas.

Ce sont les temps non négatifs qui rendent la règle gloutonne sûre. Considère les liens A → B de temps 2, A → C de temps 3 et C → B de temps -2. Dijkstra fixe B à 2, alors que l’itinéraire passant par C l’atteint à 1. Un signal ne peut jamais arriver avant d’être envoyé, donc tous les temps sont ici supérieurs ou égaux à 0 et la règle s’applique.

Algorithme

Construisez une liste d’adjacence de paires (next, w) pour chaque nœud.
Définissez dist[k] = 0, toutes les autres valeurs de dist à l’infini, puis ajoutez (0, k) dans un tas min.
Retirez le plus petit (t, node). Si t > dist[node], l’entrée est obsolète : ignorez-la.
Sinon, t est définitif. Pour chaque lien de node vers next de durée w, si t + w < dist[next], définissez dist[next] = t + w et ajoutez (t + w, next).
Lorsque le tas est vide, renvoyez -1 si une valeur de dist est infinie, sinon 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

La plupart des bugs ignorent le sens des liens, considèrent comme définitif le premier temps proposé à un nœud ou perdent de vue les nœuds que le signal n’atteint jamais.

Considérer les liens comme bidirectionnels. [3, 1, 2] transporte le signal de 3 vers 1 uniquement, c’est pourquoi le nœud 3 ne le reçoit jamais dans le deuxième exemple.
Utiliser une simple recherche en largeur. Elle trouve le chemin qui comporte le moins de liens, et non le plus rapide : dans le premier exemple, elle donne au nœud 2 le temps 4 via le lien direct, au lieu de 3 en passant par le nœud 3.
Marquer un nœud comme définitif au moment où il est ajouté à la file, plutôt qu’au moment où il en est retiré. Le premier temps proposé à un nœud n’est pas toujours le meilleur ; seule la plus petite entrée retirée du tas est définitive.
Oublier le -1. Prendre le maximum sans vérifier renvoie soit l’infini, soit le temps fini le plus élevé et masque le nœud qui n’a jamais reçu le signal.
Compter les nœuds à partir de 0. Les nœuds sont étiquetés de 1 à n : dimensionnez les tableaux à n+1 et excluez l’emplacement inutilisé 0 du maximum.
Débordement dû à l’infini. Si l’infini correspond au plus grand int, dist[u] + w déborde et devient un nombre négatif pour un u non atteint. Ignorez les nœuds non atteints ou utilisez une valeur telle que 10^9 qui laisse une marge.

Questions fréquentes4

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. C’est équivalent à O(E log n), puisque E est au plus égal à n². La liste d’adjacence, les temps et le tas nécessitent O(n + E) espace. L’algorithme de Bellman-Ford prend O(n · E) temps et O(n) espace.

Pourquoi l’algorithme de Dijkstra a-t-il besoin de poids non négatifs ?

Dijkstra fixe le nœud dont le temps provisoire est le plus petit et ne l’examine plus jamais. Cela n’est sûr que si aucun itinéraire ultérieur ne peut être plus court et, avec des poids non négatifs, chaque itinéraire passant par un nœud non fixé coûte au moins autant que le temps de ce nœud. Un lien négatif invalide ce raisonnement : un itinéraire passant par un nœud qui semblait plus coûteux peut finalement être moins cher. Pour les poids négatifs, utilisez Bellman-Ford.

Pourquoi ne pas utiliser BFS pour le délai de propagation du réseau ?

BFS visite les nœuds en fonction du nombre de liens qui les séparent du départ, ce qui correspond à l’ordre d’arrivée uniquement lorsque chaque lien prend le même temps. Ici, les durées des liens diffèrent, donc un itinéraire comportant plus de liens peut arriver plus tôt. Si toutes les durées étaient égales, BFS suffirait, et avec des durées de 0 et 1 seulement, un 0-1 BFS basé sur une deque fonctionne.

Peux-tu résoudre le problème du délai de transmission sur le réseau sans tas ?

Oui. Dijkstra avec un tableau simple parcourt tous les nœuds non réglés pour trouver le temps le plus court, ce qui coûte O(n²) au total et ne nécessite pas de tas. C’est le meilleur choix pour les graphes denses, où E est proche de n². Pour les graphes clairsemés, comme les grands tests ici avec 3,000 nœuds et 4,000 liens, la version avec tas effectue beaucoup moins de travail.

Python

def networkDelayTime(times, n, k):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]
n = 4
k = 1

Attendu

Network Delay Time

Fonction

Contraintes

Exemples

Indices

Solution

Recherche en profondeur qui revisite chaque fois qu’un itinéraire plus rapide est trouvé

Bellman-Ford : relâcher chaque arête jusqu’à n-1 fois

L’algorithme de Dijkstra avec un tas min

Pièges et cas limites

Questions fréquentes4

Problèmes similaires