Caminho mínimo na ausência de ciclo negativo

[Enunciado]  Seja G um grafo com custos nos arcos mas sem ciclos negativos. Seja P um caminho de custo mínimo em G. Queremos mostrar que P é essencialmente simples.  Mais precisamente, queremos mostrar que alguma subsequência de P é um caminho simples com a mesma origem de P, o mesmo término de P e o mesmo custo de P.

Prova

Seja v0-v1-…-vk a sequência de vértices de P.  Suponha que P não é simples.  Seja j o menor índice tal que vjvi para algum i < j.  Seja C o ciclo vi-vi+1-…-vj−1-vj  e Q o caminho v0-v1-…-vi-vj+1-…-vk.  Por hipótese, C tem custo positivo e P é mínimo.  Logo, o custo de Q é igual ao de P e o custo de C é nulo.

Se Q for simples, não há mais o que fazer. Senão, repita a construção com Q no lugar de P. Como o comprimento de Q é menor que o de P, esse processo termina depois de um número finito de passos e produz um caminho simples com as propriedades desejadas.