Délai du réseau et reconstruction du chemin
Résolvez network-delay-time avec Dijkstra, reconstruisez le plus court chemin réel à l’aide d’une table des prédécesseurs et examinez BFS bidirectionnel pour les grands graphes.
Délai du réseau et reconstruction du chemin est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Problème du délai réseau
Délai réseau (LeetCode 743) : étant donné un réseau de n nœuds et des arêtes orientées pondérées représentant les temps de propagation du signal, trouvez le temps minimal nécessaire à un signal envoyé depuis le nœud k pour atteindre tous les nœuds. Si un nœud est inaccessible, renvoyez -1. Il s’agit d’une application directe de Dijkstra : la réponse est la plus grande distance parmi les plus courts chemins depuis k vers tous les nœuds.
Solution : Dijkstra + maximum des distances
Exécutez Dijkstra depuis la source k pour trouver dist[v] pour tous les nœuds v. La réponse est max(dist.values()). Si une valeur dist[v] est encore égale à inf, ce nœud est inaccessible : renvoyez -1. Le signal emprunte simultanément tous les chemins ; le goulot d’étranglement est donc le nœud dont l’atteinte prend le plus de temps.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2Reconstruction du chemin avec le tableau des prédécesseurs
Pour reconstruire le plus court chemin réel tout en calculant les distances, conservez un dictionnaire prev qui enregistre le meilleur prédécesseur de chaque nœud. Chaque fois que vous mettez à jour dist[v], définissez prev[v] = u. Une fois Dijkstra terminé, remontez depuis la destination en suivant les pointeurs prev jusqu’à atteindre la source, puis inversez le résultat pour obtenir le chemin dans le sens direct.
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]BFS bidirectionnel pour les grands graphes non pondérés
Pour les grands graphes non pondérés où une seule paire source-destination est nécessaire, le BFS bidirectionnel peut être nettement plus rapide qu’un BFS standard. Il exécute simultanément un BFS depuis la source et un autre depuis la destination, puis s’arrête lorsque les deux frontières se rencontrent. Le gain de vitesse pratique est important, car chaque frontière ne doit explorer que la moitié de la profondeur du graphe : le nombre de nœuds explorés passe de O(b^d) à O(2 × b^(d/2)), où b est le facteur de branchement.
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1Quand choisir quel algorithme
Guide de décision : graphe non pondéré, paire unique → BFS ou BFS bidirectionnel. Graphe pondéré, poids non négatifs, source unique → Dijkstra. Graphe pondéré, poids potentiellement négatifs, source unique → Bellman-Ford. Toutes les paires → Floyd-Warshall (petit V) ou V × Dijkstra (graphe clairsemé). Nombre de sauts limité → Bellman-Ford modifié avec un nombre limité de passages. Expliquer à voix haute cette logique de décision lors d’un entretien démontre votre maturité algorithmique.
Trouvez la ville ayant le moins de voisines accessibles (LeetCode 1334)
Étant donné des villes reliées par des chemins pondérés et un distanceThreshold, trouvez la ville permettant d’atteindre le moins d’autres villes dans ce seuil (en cas d’égalité, préférez l’indice de ville le plus élevé). Solution : calculez les plus courts chemins entre toutes les paires avec Floyd-Warshall, puis comptez, pour chaque ville, combien d’autres villes sont accessibles dans le seuil. Renvoyez la ville dont le nombre est minimal (en cas d’égalité : indice maximal).
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3Chemin dans un DAG pondéré
Pour un graphe orienté acyclique (DAG), les plus courts (ou les plus longs) chemins peuvent être trouvés par un tri topologique suivi d’une relaxation en O(V+E), ce qui est plus rapide que Dijkstra. Traitez les nœuds dans l’ordre topologique ; lors du traitement du nœud u, relâchez toutes ses arêtes sortantes. Pour les plus longs chemins (utile pour l’ordonnancement de projets ou le chemin critique), inversez les poids ou remplacez min par max.
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return distPlus court chemin dans une matrice avec obstacles
Une variante courante des entretiens consiste à trouver le plus court chemin dans une grille 2D allant du coin supérieur gauche au coin inférieur droit, certaines cellules pouvant être bloquées. Il s’agit d’un problème de BFS non pondéré (chaque déplacement coûte 1). Utilisez un BFS avec des déplacements dans les quatre directions et marquez les cellules comme visitées lors de leur mise en file, et non lors de leur retrait, afin d’éviter de les revisiter. Si les obstacles peuvent être traversés moyennant un coût, utilisez Dijkstra sur la grille 2D en la considérant comme un graphe pondéré.
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4BFS à sources multiples
Lorsque plusieurs points de départ existent (par exemple, plusieurs « portes » dans une grille ou plusieurs origines sur une carte), exécutez un BFS à sources multiples : mettez simultanément toutes les sources en file avec une distance de 0. Cela calcule, en un seul parcours BFS, la distance la plus courte entre chaque cellule et la source la plus proche. Cette technique évite d’exécuter un BFS séparément depuis chaque source et s’effectue en O(V+E) au total.
Récapitulatif de la sélection des algorithmes
Un arbre de décision concis : source unique, poids non négatifs → Dijkstra O((V+E) log V). Source unique, poids négatifs → Bellman-Ford O(VE). Toutes les paires, petit V → Floyd-Warshall O(V³). DAG, poids quelconques → tri topologique + relaxation O(V+E). Graphe non pondéré → BFS O(V+E). Chemins dans une grille → BFS (non pondéré) ou Dijkstra avec un tas (pondéré). Mémorisez ce tableau : il vous permettra de répondre aux questions de suivi lors de tout entretien portant sur les plus courts chemins.
Recherche de chemins dans les questions d’entretien
De nombreux problèmes d’entretien demandent le chemin réel, et pas seulement son coût. Clarifiez toujours : avez-vous besoin du chemin ou seulement de la distance ? Si le chemin est nécessaire, allouez dès le départ un dictionnaire prev. Erreurs courantes : oublier d’initialiser prev[source] = None comme condition d’arrêt et confondre l’ordre de reconstruction (remonter de la destination vers la source, puis inverser). Entraînez-vous à reconstruire des chemins sur des exemples de 3 ou 4 nœuds avant de passer à des problèmes plus grands.
Vérification rapide
Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation de cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : le problème du délai réseau se résout avec max(dist.values()) après l’exécution de Dijkstra, la reconstruction de chemin utilise un tableau prev mis à jour chaque fois que dist[v] s’améliore, et le BFS bidirectionnel peut réduire de moitié l’espace de recherche pour les plus courts chemins non pondérés entre une paire de nœuds. Ensuite, nous aborderons l’ordonnancement des graphes avec l’algorithme de Kahn pour le tri topologique.
Questions Fréquemment Posées
La leçon « Délai du réseau et reconstruction du chemin » est-elle gratuite ?
Oui — le texte complet de « Délai du réseau et reconstruction du chemin » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Délai du réseau et reconstruction du chemin » ?
Résolvez network-delay-time avec Dijkstra, reconstruisez le plus court chemin réel à l’aide d’une table des prédécesseurs et examinez BFS bidirectionnel pour les grands graphes. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Délai du réseau et reconstruction du chemin » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Algorithme de Dijkstra avec file de priorité
- Bellman-Ford et cycles négatifs
- Floyd-Warshall : plus courts chemins entre toutes les paires
- Délai du réseau et reconstruction du chemin