[Enunciado] Seja s um vértice de um grafo G com custos nos arcos. Suponha que todos os vértices de G estão ao alcance de s. Suponha que G não tem ciclos negativos. Queremos provar que o vetor das distâncias a partir de s é um potencial relaxado.
Seja d[ ] o vetor das distâncias a partir de s. É preciso mostrar que d[ ] deixa relaxados todos os arcos de G. Seja, pois, v-w um arco de G e P um caminho mínimo de s a v. É claro que o custo de P é d[v]. Podemos supor, sem perda de generalidade, que P é simples. Logo, v-w não é arco de P. Assim, P-v-w é um caminho de s a w. Esse caminho tem custo d[v] + c, sendo c o custo de v-w. Logo, d[v] + c ≥ d[w] . Portanto, v-w está relaxado.