O problema do caminho mínimo com custos negativos

Neste problema recebemos como entrada:

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

E queremos encontrar:

 - o valor do caminho mínimo de s até cada vértice v em V
 - também gostaríamos que esses caminhos fossem devolvidos



Lembrando que quando os custos são não negativos o algoritmo guloso de Dijkstra resolve o problema em tempo O(m log n), mas não garante a corretude da solução na presença de arestas de custo negativo.

 - Note que, embora arestas de custo negativo a princípio possam não fazer sentido quando pensamos em representar grandezas físicas como distância ou tempo
 
 - o problema de caminhos mínimos modela cenários mais gerais que esses, i.e., a sequência de decisões de menor custo total para chegar num objetivo, 
 
    - onde essas decisões podem representar ganhos ou perdas de algum recurso, como em operações financeiras, manutenção de energia, etc.



Temos ainda que definir mais precisamente o que é um caminho mínimo quando existem circuitos de custo negativo

 - isso porque, se circuitos puderem fazer parte do caminho, na presença de um circuito negativo o caminho mínimo até um vértice tem custo arbitrariamente pequeno (tendendo a menos infinito)
 
    - basta percorrer o circuito inúmeras vezes antes de ir ao destino (veja exemplo)

 - por outro lado, se não permitirmos que circuitos façam parte do caminho (o que é bem razoável) o problema se torna NP-Difícil
 
    - isso significa que ele não é tratável, i.e., não existe algoritmo polinomial para ele a menos que P=NP
	
       - veremos a relevância dessa questão no fim da disciplina
	
	- só pela curiosidade, para demonstrar que tal problema é NP-Difícil, podemos reduzir o problema do Caminho Hamiltoniano (que é NP-Completo) para ele
	
	   - também veremos o que são problemas NP-Completos e NP-Difíceis no fim da disciplina

 - nossa definição temporária para o problema de caminhos mínimos será:
 
    - permitir que circuitos façam parte de caminhos
	
	   - pois assim o problema continua tratável
	
	- supor que o grafo de entrada não possui circuitos negativos
	
	   - pois nesse caso um circuito nunca fará parte de um caminho mínimo
	   
	      - para perceber isso, suponha que um caminho mínimo contém um circuito não negativo. Note que, removendo este circuito o caminho continua conectando a origem ao destino e seu custo não aumentou.
		  
	- esta última suposição acabará não sendo necessária 
	
	   - isso porque, como veremos, nosso algoritmo será capaz de identificar os circuitos negativos do grafo de entrada, caso ele os possua.