algFloydWarshall(G=(V,E), c) {

	para i = 1 até n
		para j = 1 até n
			se i = j então A[i, j, 0] = 0
			senão se (i, j) \in E então A[i, j, 0] = c(i, j)
			senão A[i, j, 0] = +\infinity
	
	para k = 1 até n
		para i = 1 até n
			para j = 1 até n
				A[i, j, k] = min{A[i, j, k-1], A[i, k, k-1] + A[k, j, k-1]}


Eficiência: \Theta(n^3), três laços aninhados, cada um indo de 1 até n, e resolver a recorrência leva tempo constante.



Extra:

 - Como detectar circuito negativo?
 
    - Basta percorrer a diagonal A[i, i, n], para i = 1, ..., n
	
	   - se não houver circuito negativo ela estará preenchida de zeros
	   
	   - se houver, ao menos alguma posição terá valor negativo
	   
	- Para obter alguma intuição do por que isso ocorre, considere que existe um circuito negativo

       - seja k o vértice de mais alto índice na nossa ordem, i.e., o último a do circuito a ser permitido num subproblema
	   
	   - seja i um outro vértice do circuito
	   
	- Considere a iteração do algoritmo em que A[i, i, k] é calculado
	
	   - pela recorrência, temos que A[i, k, k-1] + A[k, i, k-1] será considerado
	   
	      - mas este é exatamente o valor do circuito negativo
		  
	   - Assim, nesta iteração A[i, i, k] receberá um valor negativo, o qual será passado adiante até o final do algoritmo.



 - Como reconstruir a solução?
 
    - Como nossa recorrência basicamente decide se um vértice intermediário é ou não usado no caminho mínimo entre dois pontos
	
	- para reconstruir a solução podemos usar uma matriz auxiliar B[i, j] cujo valor é o vértice intermediário de mais alto índice usado no caminho mínimo de i até j
	
	- Assim para reconstruir o caminho de i até j 
	
	   - colocamos o vértice em B[i, j] no meio do caminho sendo construído
	   
	   - recursivamente reconstruímos a primeira parte do caminho de i até B[i, j]
	   
	   - recursivamente reconstruímos a segunda parte do caminho de B[i, j] até j