Corrigência do algoritmo Bellman-ford, ainda podemos fazer melhor?

Question

Eu aprendi que o algoritmo do Bellman-Ford tem um tempo de execução de O (| e | * | v |), no qual o e é o número de bordas e v o número de vértices.Suponha que o gráfico não tenha ciclos ponderados negativos.

minha primeira pergunta é que como provamos que dentro (| v | -1) iterações (cada iteração verifica cada edição e), atualiza o caminho mais curto para cada nó possível, dado um nó inicial específico?É possível que tenhamos iterated (| v | -1) vezes, mas ainda não acabar com os caminhos mais curtos para cada nó?

Assuma a exatidão do algoritmo, podemos realmente fazer melhor que isso?Ocorre-me que nem todas as bordas são pesadas negativamente em um gráfico específico.O algoritmo Bellman-Ford parece caro, como toda iteração que passa por todas as bordas.

Answer 1

O caminho mais longo possível da fonte para qualquer vertical envolveria no máximo todos os outros vértices no gráfico. Em outras palavras - você não terá um caminho que passa pelo mesmo vértice mais de uma vez, já que isso iria necessariamente aumentar os pesos (isso é verdade apenas graças ao fato de não há ciclos negativos).
Em cada iteração, você atualizaria o peso do caminho mais curto no próximo vértice nesse caminho, até depois | V | -1 iterações suas atualizações teriam que chegar ao final desse caminho. Depois disso, não haverá nenhum vértice com valores não rígidos, já que sua atualização cobriu todos os caminhos mais curtos até esse comprimento.

Essa complexidade é apertada (pelo menos para bf), pense em uma longa linha de vértices conectados. Escolha a mais à esquerda quanto a fonte - Seu processo de atualização teria que trabalhar de lá para o outro lado uma vez vértice de cada vez. Agora você pode argumentar que você não precisa verificar cada borda dessa maneira, então vamos jogar em algumas bordas aleatórias com um peso muito grande (n> | v | * max-peso) - eles não podem ajudá-lo, mas Seu algoritmo não consegue saber que, com certeza, então, se deve passar pelo processo de atualização dos vértices com esses pesos (eles ainda são melhores que o infinito inicial).