Lista 1 - comentários e correção

• Questão 1
  Nesta questão podíamos ter uma família de contra-exemplos. Bastava observar que o erro ocorria quando o caminho mais curto em um grafo com custos negativos tinha comprimento grande. Como cada arco recebia uma penalidade p, um caminho de comprimento k será penalizado em kp.

• Questão 2
  A solução mais simples para esta questão era um argumento simples de contagem. Você supõe que existe um circuito negativo C. Se este circuito não é encontrado no último loop, então, para todo arco de C vale que d(j) < d(i) + c(ij). Somando todos os arcos de C, as distâncias se anulam (aparecem uma vez de cada lado da desiguldade), e resta que a soma dos custos dos arcos do circuito é não negativa, uma contradição.

• Questão 3
  Algumas pessoas mostraram que os algoritmos que conhecemos não funcionam com esta idéia, já que surge um circuito negativo para todo arco de custo negativo. Outras mostraram que o problema pode ser corretamente reduzido usando a idéia. Ambas as soluções foram aceitas.

• Questão 4
  Para mostrar que o algoritmo de Prim está correto, podemos usar a seguinte idéia. Tome uma árvore de custo mínimo com a maior intersecção possível com a árvore gerada pelo algoritmo de Prim. Ordene os arcos na mesma ordem que são introduzidos no algoritmo de Prim, e considere o primeiro momento em que as duas árvores diferem. Neste ponto podemos considerar o que ocorreria se incluíssemos o arco que o algoritmo de Prim escolhe na árvore ótima, e construiríamos uma outra árvore com o mesmo custo e maior intersecção com a árvore de Prim, uma contradição.

• Questão 5
  Dei dez pontos para quem implementou um algoritmo para caminho mínimo (Dijkstra ou Bellman Ford). Quanto aos relatórios, esperava mais detalhes de estruturas de dados utilizadas, resultados de testes, etc.