Detecção de ciclo negativo usando Bellman-Ford e sua exatidão

Question

Eu recentemente comecei a estudar algoritmos sozinhos usando Vídeos Cormen e MIT Algo no YouTube. Eu estou indo através de Bellman-Ford.

Eu tenho 2 dúvidas sobre a exatidão do algoritmo:

.

1. Por que estamos relaxando (num dos vértices - 1) vezes todas as bordas? Por que não algum número finito de vezes até valores anteriores e novos valores permanecem iguais?

2. O segundo para loop (linhas 5,6,7 na imagem Algo) é para detectar ciclos de borda negativos. Então eu passei por essa exatidão. Eu vi um teorema que se houver um ciclo de borda negativo acessível a partir da fonte, então podemos encontrar uma UV de borda tal que d (v)> d (u) + w (u, v) [eu entendi a prova pela contradição ( Se somar todos os vértices de ciclo de borda negativa resultar em soma de todos os pesos ao longo de positivo do ciclo negativo, o que significa contradição, pois deve ser negativo - página 2 de https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf] < / p>

Mas eu não sou capaz de visualizar essa borda se eu tiver algum ciclo de borda negativa do vértice de origem s. Por favor me ajude: Como essa vantagem pode existir?

Answer 1

Se não houver ciclos negativos, você pode realmente executar o relaxamento até que todos os valores permaneçam os mesmos. Na $ i $ i $ -th rodada de relaxamento você tem assegurado para ter calculado corretamente todas as distâncias finitas em relação a todos os vértices cuja distância de Hop-Span's CLASS=" "> $ S $ é no máximo $ i $ (a distância de salto é o número de bordas em um caminho mais curto).

Portanto, parando após a $ (N-1) $ -th Iteration assegura que:

• Todas as distâncias finitas foram corretamente computadas
• O algoritmo termina em gráficos com ciclos negativos.

Observe que há gráficos onde todas as iterações de $ (N-1) $ são necessárias para calcular corretamente as distâncias. Por exemplo, um caminho.

Com relação a 2), sua pergunta não está completamente clara para mim. Na prova não há uma borda particular para visualizar. A prova mostra que, se impossível, para essas duas condições serem simultaneamente verdadeiras:

• há algum ciclo de peso negativo $ c $ .
• nenhum relaxamento acontece, ou seja, $ vd \ le ud + w (u, v) $ para todos os vértices $ V $ do ciclo. Isso é usado na segunda desigualdade centrada.