[Enunciado] Seja G um grafo sem ciclos negativos ao alcance de um vértice s. Seja P um caminho mínimo com origem s. Queremos mostrar que todo segmento inicial de P é um caminho mínimo.
Denotaremos por c(vw) o custo de um arco v-w e por c(C) o custo de um caminho C.
Seja Q um segmento inicial de P e R o correspondente segmento final. Seja v o término de Q (e portanto também a origem de R). Seja M um caminho mínimo de s a v em G. Pelo Lema 1 abaixo,
c(M) + c(R) ≥ c(P).
Segue daí que c(M) + c(R) ≥ c(Q) + c(R) e portanto c(M) ≥ c(Q). Concluímos que Q é mínimo.
Lema 1: Sejam s um vértice e R um caminho num grafo com custos nos arcos. Seja M um caminho mínimo de s até a origem de R. Seja P um caminho mínimo de s o término de R. Se o grafo não tem ciclos negativos ao alcance de s então c(M) + c(R) ≥ c(P).
Prova: Suponha que (v0, v1, … vq−1, vq) é a sequência de vértices de R. Para cada índice i, seja Si um caminho mínimo de s a vi. É claro que c(S0) = c(M) e c(Sq) = c(P). Pelo lema 2 abaixo, com Si no papel de M e com vi-vi+1 no papel de v-w,
| c(M) + c(R) | = | c(S0) + c(v0v1) + c(v1v2) + … + c(vq−1vq) |
| ≥ | c(S1) + c(v1v2) + … + c(vq−1vq) | |
| ⋮ | ||
| ≥ | c(Sq−1) + c(vq−1vq) | |
| ≥ | c(Sq) | |
| = | c(P) . |
Lema 2: Seja s um vértice e v-w um arco de um grafo com custos nos arcos. Seja M um caminho mínimo de s a v e P um caminho mínimo de s a w. Se não há ciclo negativo ao alcance de s então c(M) + c(vw) ≥ c(P).
Prova: Como não há ciclos negativos ao alcance de s, podemos supor que M é simples. Portanto, M não passa por v-w. Assim, a concatenação de M com v-w é um caminho. O custo desse caminho é c(M) + c(vw). Como P é mínimo, c(P) ≤ c(M) + c(vw).