Algoritmo de Bellman-Ford - Por que as bordas podem ser atualizadas fora de ordem?

O algoritmo de Bellman-Ford determina o caminho mais curto de uma fonte para todos os outros vértices. Inicialmente, a distância entre s e todos os outros vértices é definida como ∞ . Então, o caminho mais curto de s para cada vértice é calculado; isso continua por | V | - 1 iterações. Minhas perguntas são:$s$$s$$\infty$$s$$|V|-1$

• Por que precisa haver iterações?$|V|-1$
• Importa se eu verifiquei as bordas em uma ordem diferente?
  Por exemplo, se eu checar as arestas 1,2,3, mas na segunda iteração checarei 2,3,1.

Eric disse que a ordem não importava, mas isso me confunde: o algoritmo não atualizaria incorretamente um nó com base na aresta se seu valor dependesse da aresta x 1, mas x 1 é atualizado após x 2 ?$x_2$$x_1$$x_1$$x_2$

Considere o caminho mais curto de a t , s , v 1 , v 2 , … , v k , t . Este caminho consiste em no máximo | V | - 1 arestas, porque repetir um vértice no caminho mais curto é sempre uma má ideia (ou pelo menos existe um caminho mais curto que não repita vértices), se não tivermos ciclos de peso negativos.$s$$t$$s, v_1, v_2, \dots, v_k, t$$|V|-1$

Na primeira rodada, sabemos que a aresta será relaxada; portanto, a distância estimada para v 1 estará correta após essa rodada. Observe que não temos idéia do que é v 1 neste momento, mas como relaxamos todas as arestas, devemos ter relaxado essa também. Na segunda rodada, relaxamos ( v 1 , v 2 ) em algum momento. Ainda não temos idéia do que v 1 ou v 2 são, mas sabemos que suas estimativas de distância estão corretas.$(s, v_1)$$v_1$$v_1$$(v_1, v_2)$$v_1$$v_2$

Repetindo isso, depois de alguma rodada , relaxamos ( v k , t ) , após o qual a estimativa de distância para t está correta. Não temos idéia do que é k até que todo o algoritmo termine, mas sabemos que isso acontecerá em algum momento (supondo que não haja ciclos de peso negativos).$k+1$$(v_k, t)$$t$$k$

Portanto, a observação crucial é que, após a rodada , o i- ésimo nó do caminho mais curto deve ter sua estimativa de distância definida no valor correto. Como o caminho é no máximo | V | - 1 aresta de comprimento, | V | - 1 rodada é suficiente para encontrar o caminho mais curto. Se um | V | A rodada ainda muda algo, então algo estranho está acontecendo: todos os caminhos já devem estar "estabelecidos" para seus valores finais, portanto, devemos ter a situação de que existe algum ciclo de peso negativo.$i$$i$$|V|-1$$|V|-1$$|V|$

O maior caminho que um caminho pode ter sem ciclos é |V|. Começamos com uma fonte; portanto, já temos um caminho de comprimento 1; portanto, precisamos de |V| - 1mais nós para obter o caminho mais longo.

O pedido não importa, pois todo pedido manterá a invariante: após as niterações, o valor de cada nó é menor ou igual ao custo do caminho de custo mínimo sdo nó que contém no máximo narestas.

Se, no início de uma iteração, o custo estiver correto até nnós, no final da iteração, estará correto até n+1nós. Uma reordenação pode fazer com que alguns nós tenham um custo menor antes de serem atualizados normalmente, mas acabam sendo atualizados de qualquer maneira.