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

1 -	construa G' adicionando vértice s e uma aresta de s até cada v em V com custo 0
	
2 -	execute o algoritmo de Bellman-Ford em G' com custos c a partir de s
	
	para cada vértice v em V seja pv = caminho mínimo encontrado pelo algoritmo de Bellman-Ford
	
3 -	para cada aresta (u, v) em E calcule custos c'(u, v) = c(u, v) + pu - pv
	
4 -	para cada vértice v em V execute o algoritmo de Dijkstra em G com custos c' a partir de v
	
	sejam d'(u, v) as distâncias obtidas pelas diversas execuções do algoritmo de Dijkstra
	
5 -	para cada par de vértices u, v em V calculce d(u, v) = d'(u, v) - pu + pv

}

Eficiência:

1 - \Theta(n)

2 - \Theta(n m)

3 - \Theta(m)

4 - n * \Theta(m log n) = \Theta(n m log n)

5 - \Theta(n^2)

como n = O(m) o tempo do algoritmo é dominado por \Theta (n m log n)

 - que supera o algoritmo de Floyd-Warshall em grafos esparsos



Corretude: depende de dois fatores

1) a mudança de custos não altera a ordem relativa entre os caminhos com mesma origem e destino

2) a mudança de custos torna todos os custos não negativos



Para verificar que 1) ocorre, tome um caminho qualquer P entre i e j

 - caculando o custo original de P temos
 
	c(P) = \sum_{e \in P} c(e)

 - calculando o custo modificado de P temos 

	c'(P) = \sum_{e \in P} c'(e) 
		  = \sum_{e=(u,v) \in P} (c(e) + pu - pv) 
		  = pi - pj + \sum_{e=(u,v) \in P} c(e)
		  = pi - pj + c(P)

    - onde a penúltima desigualdade vale pois para cada vértice v interno do caminho pv aparece duas vezes no somatório, uma vez com sinal positivo e outra vez com sinal negativo
	
    - note que, independente de qual seja o caminho P entre i e j, a diferença entre c(P) e c'(P) depende apenas de pi e de pj
	
       - portanto, a mudança de custos não altera a ordem relativa entre os caminhos com mesma origem e destino
	   
	- o resultado c(P) = c'(P) - pi + pj também explica o calculo feito no passo 5 do algoritmo



Para verificar que 2) ocorre, note que o valor pu para um vértice u qualquer corresponde ao caminho mínimo de s até u

 - lembrando que s tem uma aresta de custo zero entrando em todos os vértices

 - portanto, o custo de tais caminhos será sempre <= 0

Considere uma aresta (u, v) qualquer

 - um caminho possível para ir de s até v é
 
    - ir de s até u de então usar a aresta (u, v). Portanto 
	
		pv <= pu + c(u, v) --> c(u, v) + pu - pv >= 0
		
	- mas isso conclui a demonstração, pois 
	
		c'(u, v) = c(u, v) + pu - pv
		
	- portanto, c'(u, v) >= 0

 - como tomamos uma aresta qualquer, mostramos que 
 
    - a mudança de custos torna todos os custos não negativos