Algoritmo Bellman Ford: guia de entrevista de codificação

DR: O algoritmo Bellman Ford encontra caminhos mais curtos de fonte única em um gráfico direcionado ponderado, mesmo quando algumas arestas têm pesos negativos. Inicialize a distância da fonte para zero, todas as outras para o infinito, relaxe cada aresta até V menos 1 vezes e, em seguida, faça uma passagem extra: qualquer melhoria adicional prova que existe um ciclo de peso negativo alcançável.

Qual é o algoritmo Bellman Ford?

Bellman Ford é um algoritmo de caminho mais curto de estilo de programação dinâmica. Após a primeira passagem completa, os caminhos mais conhecidos utilizam no máximo uma aresta; após a segunda, no máximo duas arestas. Um caminho simples contém no máximo V menos 1 arestas, o que explica tanto a contagem de loops quanto o argumento de correção. Ao contrário do algoritmo de Dijkstra, Bellman Ford não assume pesos de aresta não negativos.

Como você explica o relaxamento extremo?

Para uma aresta de u a v com peso w, o relaxamento pergunta se a distância[u] + w é menor que a distância[v]. Execute a adição somente quando u estiver acessível. Se o candidato for melhor, atualize a distância[v] e defina o antecessor[v] como u. A matriz predecessora é opcional para distâncias, mas permite reconstruir o caminho real e explicar claramente o resultado.

Como você rastreia Bellman Ford em uma entrevista?

Use um gráfico pequeno e escreva uma linha de distância por passagem. Comece com a fonte A em 0 e todos os outros vértices no infinito. Digitalize a lista completa de bordas em uma ordem consistente, registrando cada atualização. Pare cedo quando uma passagem inteira não causar alterações. Seja explícito que a ordem das arestas pode alterar as linhas intermediárias, mas não as distâncias finais corretas quando não existe nenhum ciclo negativo alcançável.

Que pseudocódigo você deve escrever?

Crie matrizes de distância e predecessoras e repita uma varredura completa da borda V menos 1 vezes. Use um sinalizador alterado para rescisão antecipada. Finalmente, verifique todas as arestas mais uma vez e relate um ciclo negativo se a distância alcançável ainda puder melhorar. No código de produção, escolha um tipo numérico que possa conter somas de caminhos e proteger a sentinela do infinito antes da adição.

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

A implementação padrão da lista de arestas de adjacência é executada em tempo O(VE) porque pode varrer arestas E em cada uma das passagens V menos 1, mais uma passagem de detecção. Ele usa espaço auxiliar O(V) para distâncias e predecessores. A parada antecipada melhora os insumos favoráveis, mas o limite do pior caso permanece O(VE).

Quando você deve escolher Bellman Ford em vez de Dijkstra?

Escolha Bellman Ford quando pesos de borda negativos forem permitidos ou quando o entrevistador solicitar explicitamente detecção de ciclo negativo alcançável. Escolha Dijkstra com uma fila de prioridade para gráficos cujos pesos de aresta são todos não negativos porque normalmente é mais rápido. Para caminhos mais curtos de todos os pares, primeiro esclareça a densidade do gráfico, os pesos negativos e se são necessários caminhos ou apenas distâncias.

Quais erros você deve evitar?

Não relaxe a partir de um vértice inacessível, confunda uma aresta negativa com um ciclo negativo ou afirme que todo ciclo negativo invalida o resultado: apenas um ciclo acessível a partir da fonte afeta seus caminhos mais curtos. Evite também executar apenas V menos 2 passagens, pular a passagem de detecção final ou reconstruir um caminho sem manter os predecessores.

Como você pode praticar a explicação?

Pratique três versões: uma definição de 30 segundos, uma explicação de correção de dois minutos e uma implementação completa. Teste um vértice inacessível, uma aresta negativa sem ciclo, um ciclo negativo alcançável e um gráfico que se estabilize antecipadamente. Isso separa o código memorizado da compreensão genuína.

Use a IA para organizar o material que você já entende, ensaie explicações e analise seu desempenho. Siga as regras do empregador e do fornecedor de avaliação e nunca invente experiências, números ou resultados.

Continue com o guia do copiloto de entrevista de IA, preparação baseada no currículo e fluxo de trabalho de revisão pós-entrevista.

Perguntas frequentes

Pratique com evidências, não com um roteiro

YesToTheOffer pode basear a preparação e a estrutura de respostas em tempo real em seu currículo, descrição da função e notas privadas e, em seguida, preservar uma transcrição para revisão pós-entrevista.