O problema dos caminhos mínimos de todos para todos

Neste problema recebemos como entrada:

 - um grafo orientado (ou dirigido) G=(V,E), 
 - com custo c(e) em cada aresta e em E

E queremos encontrar:

 - o valor do caminho mínimo de u até v para todo par u, v em V
 - também gostaríamos que esses caminhos fossem devolvidos
 
No caso de haver um circuito negativo na entrada

 - o valor dos caminhos mínimos não está bem defido
 - por isso, tal fato deve ser reportado



Com o conhecimento que já temos, podemos resolver esse problema

 - uma estratégia é executar um algoritmo de caminhos mínimos a partir de cada vértice
 - este procedimento leva tempo

	n * Tempo do algoritmo de caminhos mínimos

 - se os custos da entrada são não negativos
 
    - podemos usar o algoritmo de Dijkstra, que leva tempo 
	
		\Theta(m log n)
	
    - portanto, nosso algoritmo para encontrar caminhos mínimos de todos para todos levará tempo 
	
		n * \Theta(m log n) = \Theta(n m log n)
		
       - se o grafo é esparço, i.e., m = \Theta(n) temos \Theta(n m log n) = \Theta (n^2 log n)
	
	      - que é muito bom, já que, apenas para devolver os valores das soluções, precisamos preencher n^2 posições
	
	   - se o grafo for denso, i.e., m = \Theta(n^2) temos \Theta(n m log n) = \Theta (n^3 log n)
	
	      - que é razoável, já que gastamos pouco mais que tempo linear por caminho mínimo encontrado

 - se os custos da entrada podem ser negativos
 
    - temos que usar o algoritmo de Bellman-Ford, que leva tempo
	
		\Theta(n m)
	
    - portanto, nosso algoritmo para encontrar caminhos mínimos de todos para todos levará tempo 
	
		n * \Theta(n m) = \Theta(n^2 m)
		
       - se o grafo é esparço, i.e., m = \Theta(n) temos \Theta(n^2 m) = \Theta (n^3)
	
	      - que é razoável, já que gastamos tempo linear por caminho mínimo encontrado
	
	   - se o grafo for denso, i.e., m = \Theta(n^2) temos \Theta(n^2 m) = \Theta (n^4)
	
	      - que embora seja polinomial, i.e., muito melhor que buscas exaustivas exponenciais, já não é tão bom



Veremos um algoritmo de programação dinâmica que explora uma subestrutura ótima diferente daquela do algoritmo de Bellman-Ford e obtém soluções em tempo \Theta(n^3), independente da densidade do grafo.