Tempo de atraso da rede e reconstrução de caminhos
Resolva o problema do tempo de atraso da rede com Dijkstra, reconstrua o caminho mínimo real usando um mapa de predecessores e discuta BFS bidirecional para grafos grandes.
Tempo de atraso da rede e reconstrução de caminhos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Problema Network Delay Time
Network Delay Time (LeetCode 743): dada uma rede com n nós e arestas direcionadas ponderadas que representam os tempos de propagação do sinal, encontre o tempo mínimo para um sinal enviado do nó k alcançar todos os nós. Se algum nó não for alcançável, retorne -1. Esta é uma aplicação direta de Dijkstra: a resposta é a maior distância de caminho mais curto a partir de k entre todos os nós.
Solução: Dijkstra + máximo das distâncias
Execute Dijkstra a partir da origem k para encontrar dist[v] para todos os nós v. A resposta é max(dist.values()). Se algum dist[v] ainda for inf, esse nó não é alcançável — retorne -1. O sinal percorre todos os caminhos simultaneamente; portanto, o gargalo é o nó que leva mais tempo para ser alcançado.
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)) # 2Reconstrução de caminhos com o vetor prev
Para reconstruir o caminho mais curto real enquanto calcula as distâncias, mantenha um dicionário prev que registre o melhor predecessor de cada nó. Sempre que atualizar dist[v], defina prev[v] = u. Depois que Dijkstra terminar, percorra os ponteiros de prev para trás a partir do destino até alcançar a origem e, em seguida, inverta o resultado para obter o caminho no sentido correto.
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 bidirecional para grafos grandes não ponderados
Para grafos grandes não ponderados em que é necessário apenas um par origem-destino, a BFS bidirecional pode ser significativamente mais rápida que a BFS padrão. Ela executa BFS simultaneamente a partir da origem e do destino, parando quando as duas fronteiras se encontram. O ganho de velocidade na prática é significativo porque cada fronteira precisa explorar apenas metade da profundidade do grafo — reduzindo os nós explorados de O(b^d) para O(2 × b^(d/2)), em que b é o fator de ramificação.
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 -1Quando escolher cada algoritmo
Guia de decisão: grafo não ponderado, par único → BFS ou BFS bidirecional. ponderado, não negativo, fonte única → Dijkstra. ponderado, possivelmente negativo, fonte única → Bellman-Ford. todos os pares → Floyd-Warshall (V pequeno) ou V × Dijkstra (grafo esparso). saltos com restrições → Bellman-Ford modificado com passagens limitadas. Explicar essa justificativa de decisão em voz alta nas entrevistas demonstra maturidade algorítmica.
Encontre a cidade com menos vizinhos alcançáveis (LeetCode 1334)
Dadas cidades com caminhos ponderados e um distanceThreshold, encontre a cidade alcançável a partir de menos outras cidades dentro do limite (em caso de empate, prefira o maior índice da cidade). Solução: calcule os caminhos mais curtos entre todos os pares com Floyd-Warshall e, em seguida, conte para cada cidade quantas outras cidades são alcançáveis dentro do limite. Retorne a cidade com a menor contagem (em caso de empate: o maior índice).
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)) # 3Caminho em um DAG ponderado
Para um grafo acíclico direcionado (DAG), os caminhos mais curtos (ou mais longos) podem ser encontrados com ordenação topológica + relaxamento em O(V+E) — mais rapidamente que com Dijkstra. Processe os nós na ordem topológica; ao processar o nó u, relaxe todas as arestas que saem dele. Para caminhos mais longos (úteis no agendamento de projetos / caminho crítico), negue os pesos ou troque o mínimo pelo máximo.
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 distCaminho mais curto em uma matriz com obstáculos
Uma variante comum em entrevistas: encontre o caminho mais curto em uma grade 2D do canto superior esquerdo ao canto inferior direito, em que algumas células podem estar bloqueadas. Este é um problema de BFS não ponderado (cada passo custa 1). Use BFS com movimento nas 4 direções, marcando as células como visitadas quando forem enfileiradas (não quando forem retiradas da fila) para evitar revisitá-las. Se for possível atravessar obstáculos (com um custo), use Dijkstra na grade 2D, tratando-a como um grafo ponderado.
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 com múltiplas fontes
Quando existem vários pontos de partida (por exemplo, vários “portões” em uma grade ou várias origens em um mapa), execute uma BFS com múltiplas fontes: enfileire todas as fontes simultaneamente, com distância 0. Isso calcula a menor distância da fonte mais próxima até cada célula em uma única passagem de BFS. Essa técnica evita executar BFS separadamente a partir de cada fonte e tem complexidade total O(V+E).
Recapitulação da seleção de algoritmos
Uma árvore de decisão concisa: fonte única, pesos não negativos → Dijkstra O((V+E) log V). Fonte única, pesos negativos → Bellman-Ford O(VE). Todos os pares, V pequeno → Floyd-Warshall O(V³). DAG, quaisquer pesos → ordenação topológica + relaxamento O(V+E). Não ponderado → BFS O(V+E). Caminhos em grade → BFS (não ponderado) ou Dijkstra com fila de prioridade (ponderado). Memorize esta tabela — ela responde às perguntas de acompanhamento em qualquer entrevista sobre caminhos mais curtos.
Busca de caminhos em questões de entrevista
Muitos problemas de entrevista pedem o caminho real, não apenas o custo. Esclareça sempre: você precisa do caminho ou apenas da distância? Se o caminho for necessário, aloque um dicionário prev desde o início. Erros comuns: esquecer de inicializar prev[source] = None como condição terminal e confundir a ordem de reconstrução (voltar do destino até a origem e, em seguida, inverter). Pratique a reconstrução de caminhos em exemplos com 3 a 4 nós antes de aplicá-la a problemas maiores.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: Network Delay Time é resolvido por max(dist.values()) após Dijkstra, a reconstrução de caminhos usa um vetor prev atualizado sempre que dist[v] melhora e a BFS bidirecional pode reduzir pela metade o espaço de busca de caminhos mais curtos não ponderados entre um único par. Em seguida, estudaremos a ordenação de grafos com o algoritmo de Kahn para ordenação topológica.
Perguntas Frequentes
A aula “Tempo de atraso da rede e reconstrução de caminhos” é grátis?
Sim — o texto completo de “Tempo de atraso da rede e reconstrução de caminhos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Tempo de atraso da rede e reconstrução de caminhos”?
Resolva o problema do tempo de atraso da rede com Dijkstra, reconstrua o caminho mínimo real usando um mapa de predecessores e discuta BFS bidirecional para grafos grandes. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Tempo de atraso da rede e reconstrução de caminhos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Algoritmo de Dijkstra com fila de prioridades
- Bellman-Ford e ciclos negativos
- Floyd-Warshall: caminhos mínimos entre todos os pares
- Tempo de atraso da rede e reconstrução de caminhos