Começamos imaginando uma solução ótima

Neste problema queremos encontrar o caminho mínimo do vértice s para todos os demais vértices v em V

 - mas vamos começar imaginando uma solução ótima de s para um vértice t específico

A sequência dos vértices do caminho nos dá uma ordem implícita para seguir

 - assim, olhemos para o último vértice do caminho e foquemos na última aresta do mesmo
 
 - o último vértice é t e digamos que a última aresta é (w, t)
 
 - assim, temos que nosso caminho P de s a t é composto por:
 
    - um caminho P' de s a w
	
	- uma aresta (w, t)
	
	- portanto, a relação de custo é 
	
		c(P) = c(P') + c(w, t)
	
	- normalmente daqui seguiríamos provando que P' é uma solução ótima para o subproblema, mas vamos parar antes porque esta primeira tentativa de encontrar a subestrutura ótima do problema tem uma falha.
	
	   - nós queremos definir/construir a solução ótima de um problema em função de subproblemas menores, mas não temos qualquer medida que nos diga que 
	   
	      - o problema do caminho mínimo de s a w é menor que o problema do caminho mínimo de s a tem
		  
	   - de fato, essa é uma dificuldade recorrente ao se aplicar a técnica de programação dinâmica para problemas em grafos
	   
	      - já que grafos são definidos por conjuntos (de vértices e de arestas) eles não tem ordens bem definidas que tornem óbvio dizer qual problema é maior e qual é menor
		  
	   - a solução inventiva encontrada pelo algoritmo de Bellman-Ford foi associar o tamanho do subproblema ao número de arestas permitidas no caminho



Usando esta ideia, temos a subestrutura ótima do problema

 - Para cada vértice v em V, i em {1, 2, ...}, seja P o caminho mínimo de s a v com no máximo i arestas. Temos dois casos 
 
    1) Se P tem menos que i arestas, então P é uma solução ótima do subproblema do caminho mínimo de s a v com no máximo i-1 arestas
	
	2) Se P tem i arestas, seja (w, v) a última aresta de P. Neste caso, seja P' a parte de P que vai de s até w. Temos que P' é uma solução ótima do subproblema do caminho mínimo de s a w com no máximo i-1 arestas.

Demonstração da otimalidade

 1) Supondo por contradição que P não é ótimo para o subproblema com no máximo i-1 arestas, então existe P* que é solução para este problema e c(P*) < c(P). Como P* também é solução para o problema do caminho mínimo com no máximo i arestas temos uma contradição com a hipótese de que P era ótimo.
 
 2) Supondo por contradição que P' não é ótimo para o subproblema do caminho mínimo de s a w com no máximo i-1 arestas. Seja P* um caminho de s a w com no máximo i-1 aresta e c(P*) < c(P'). Concatenando P* com (w,v) temos um caminho com no máximo i arestas e custo c(P*) + c(w,v) < c(P') + c(w,v) = c(P), o que contraria a hipótese de que P era ótimo.