Algoritmo Floyd – Warshall: guia de entrevista de codificação

DR: O algoritmo Floyd-Warshall calcula os caminhos mais curtos de todos os pares com programação dinâmica. Inicialize uma matriz de distância do gráfico e, em seguida, para cada vértice intermediário k, atualize cada par com dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Ele é executado no tempo O(V³) e no espaço O(V²) e pode expor ciclos negativos por meio de entradas diagonais negativas.

O que é o algoritmo Floyd-Warshall?

Floyd – Warshall é um algoritmo de programação dinâmica para caminhos mais curtos entre cada par ordenado de vértices. Funciona com gráficos ponderados direcionados ou não direcionados e permite arestas negativas. Se existir um ciclo de peso negativo relevante, entretanto, alguns caminhos mais curtos não têm mínimo finito porque percorrer repetidamente o ciclo continua reduzindo o custo do caminho.

O algoritmo é memorável porque transforma um problema de caminho global em uma decisão: para o vértice intermediário atual k, o caminho mais conhecido de i para j é melhor como está, ou vai de i para k e depois de k para j?

Como você deriva a recorrência?

Defina D(k, i, j) como a distância mais curta de i a j cujos vértices intermediários podem vir apenas dos primeiros k vértices. Um caminho mais curto permitido evita o vértice k, mantendo D(k−1, i, j), ou usa k e se divide no melhor caminho permitido de i a k ​​mais o melhor caminho permitido de k a j.

Isso dá a recorrência:

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

Como o estágio k depende apenas dos valores do estágio k−1 de forma compatível, a matriz pode ser atualizada no local. Este raciocínio também explica a ordem crítica do loop: k deve ser o loop mais externo. Colocar i ou j fora altera o invariante e pode usar caminhos parcialmente permitidos incorretamente.

Como você inicializa a matriz de distância?

Crie uma matriz V por V. Defina dist[i][i] como zero, defina a célula de uma aresta direta com seu peso e use infinito quando não existir aresta direta. Se forem possíveis bordas paralelas, mantenha o menor peso direto. Antes de adicionar duas distâncias, verifique se ambas são finitas para que uma sentinela do infinito não transborde ou crie um falso candidato.

Como você rastreia Floyd – Warshall em uma entrevista?

Rotule as linhas da matriz como origens e as colunas como destinos. Mostre a matriz inicial, escolha um k e avalie as células representativas. Para cada célula, compare o valor atual com a rota através de k. Atualize somente quando ambos os segmentos estiverem acessíveis e a nova soma for menor.

Normalmente não é necessário desenhar todas as matrizes para obter um exemplo grande. Trace células suficientes para demonstrar o invariante, incluindo uma melhoria e um valor inalterado. Afirme que após completar k, toda entrada da matriz é ótima entre caminhos cujos vértices intermediários são limitados ao conjunto processado.

Que pseudocódigo você deve escrever?

Use três loops aninhados com k do lado de fora:

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Explique as verificações finitas e o tipo numérico. Em idiomas com um sentinela inteiro grande, adicionar infinito a um valor negativo pode parecer finito ou excessivo. Uma guarda faz parte da correção, não apenas um detalhe de implementação.

Quais são as complexidades de tempo e espaço?

Os três loops examinam cada combinação de k, i e j, portanto o tempo de execução é O(V³). A matriz de distância ocupa o espaço O(V²). A atualização no local evita uma tabela tridimensional, enquanto uma matriz de próximo salto ou predecessora para reconstrução de caminho adiciona O(V²) mais espaço.

Floyd-Warshall costuma ser atraente para gráficos densos e modestos porque sua implementação é compacta e previsível. Para um gráfico grande e esparso com arestas não negativas, executar o Dijkstra a partir de cada fonte pode ser mais eficiente. Sempre compare a saída necessária, a densidade do gráfico, as restrições de peso e a contagem de vértices antes de escolher.

Como você reconstrói o caminho mais curto real?

As distâncias por si só não revelam a sequência de vértices. Mantenha uma matriz next[i][j] inicializada em j quando existir uma aresta direta de i para j. Sempre que o roteamento através de k melhorar dist[i][j], defina next[i][j] como next[i][k]. Para reconstruir um caminho, mova repetidamente do vértice atual para next[current][destination] até chegar ao destino.

Verifique se há pares inacessíveis antes da reconstrução e proteja contra casos de ciclo negativo. Se um par pode viajar para um ciclo negativo e então chegar ao destino, não existe um caminho mais curto e finito para reconstruir.

Como o Floyd-Warshall detecta ciclos negativos?

Após a conclusão do algoritmo, inspecione a diagonal. Um valor dist[v][v] < 0 prova que um ciclo de peso negativo é alcançável a partir de v e pode retornar a v. Isso é mais forte do que simplesmente encontrar uma aresta negativa; arestas negativas podem existir em gráficos com caminhos mais curtos perfeitamente válidos.

Se o entrevistador perguntar quais pares são afetados, identifique todos os i e j para os quais i pode alcançar tal vértice v e v pode alcançar j. Esses pares podem percorrer o ciclo negativo arbitrariamente muitas vezes, portanto o valor do caminho mais curto não é finito.

Quando você deve escolher outro algoritmo de caminho mais curto?

Use a pesquisa ampla para gráficos não ponderados, Dijkstra para problemas de fonte única com pesos não negativos e Bellman-Ford para uma única fonte quando pesos negativos ou detecção de ciclo negativo alcançável são importantes. Floyd-Warshall é a escolha direta quando as distâncias de todos os pares são necessárias e o tempo cúbico é aceitável.

Quais erros de entrevista você deve evitar?

Não coloque k dentro de outro loop, esqueça os zeros na diagonal, adicione infinito sem guarda, confunda arestas negativas com ciclos negativos ou afirme que o espaço da matriz O(V²) inclui a entrada automaticamente em cada representação. Esclareça se o gráfico é direcionado, se existem arestas paralelas e se o entrevistador precisa de distâncias, caminhos ou pares afetados por ciclos.

Pratique o fluxo de trabalho do assistente de entrevista de codificação, compare o algoritmo Bellman-Ford e revise a folha de dicas de complexidade Big O.

Perguntas frequentes

Pratique o invariante, não apenas os loops

YesToTheOffer pode ajudar a estruturar uma explicação de codificação, baseá-la em suas notas de preparação privadas, examinar casos extremos e preservar a transcrição da entrevista para revisão posterior.