Para que o algoritmo de Bellman-Ford detecte se o grafo de entrada possui circuitos negativos basta fazer as seguintes modificações

 - executar o laço mais externo do algoritmo até i = n
 
 - verificar se o valor A[i, v] muda para algum v nessa iteração
 
    - se ocorrer alguma mudança é porque existem circuitos negativos (mais precisamente, circuitos negativos alcançáveis a partir de s)



A intuição do porque isso funciona é que

 - como todo caminho com n arestas ou mais repete vértices e, portanto, tem circuitos

 - se algum caminho que utiliza no máximo n arestas tem custo menor que algum caminho que utiliza no máximo n-1 arestas
 
 - então tal caminho utiliza n aresta e, portanto, possui algum circuito negativo
 
    - de fato, para encontrar tal circuito basta seguir o caminho de trás pra frente a partir do vértice cujo cuto foi reduzido
	
	   - usando a ideia de reconstruir a solução a partir da matriz A


Para mostrar formalmente que o resultado vale, vamos provar o seguinte lema

 - G não tem circuitos negativos se, e somente se, no algoritmo de Bellman-Ford A[n-1, v] = A[n, v] para todo v em V.
 
Prova:

(-->) A ida segue da corretude do algoritmo de Bellman-Ford e do fato que, na ausência de circuitos negativos todo caminho mínimo tem no máximo n-1 arestas. Assim, A[n-1, v] já possui o valor do caminho mínimo para de s a v, para todo v, e permitir que se use uma aresta a mais de nada vai ajudar.

(<--) Na volta, considere um circuito C e vamos mostrar que ele não tem custo negativo. Note que, para cada vértice v em C, temos 

	A[n-1, v] = A[n, v] = min { A[n-1, v] , min_{(w,v) \in E} {A[n-1, w] + c(w,v) } } <= A[n-1, w] + c(w,v), 

onde a primeira igualdade vem da hipótese da volta, a segunda igualdade vem da recorrência do algoritmo, e a desigualdade vale pela definição do mínimo e para qualquer w tal que (w,v) está em E.

Sendo w o vértice que precede v em C, temos 

	A[n-1, v] <= A[n-1, w] + c(w,v)
	
	A[n-1, v] - A[n-1, w] <= c(w,v)	

Finalmente, somando o custo de todas as arestas em C temos 

	\sum_{(v,w) \in C} c(v,w) >= \sum_{(v,w) \in C} A[n-1, v] - A[n-1, w]
							  >= 0

sendo que a desigualdade segue do cancelamento dos termos A[n-1, v], já que cada um aparece duas vezes no somatório, uma vez com o sinal positivo e outra com o sinal negativo.

Assim concluímos que o custo de qualquer circuito C é não negativo quando os valores não mudam entre as iterações n-1 e n.