Tenho uma duvida sobre o que entregar como resposta deste exercicio.
"O algoritmo funciona bem? Justifique."
Caso a resposta seja "Sim", devo mostrar os invariantes e prova-los?
E caso a resposta seja "Não" devo mostrar um exemplo em que o algoritmo falha?
Apenas isso?
Estou mandando esta duvida pois sei que o monitor é exigente. =P
Se sua resposta for sim, você deve provar que o algoritmo funciona (correção) e que ele é competitivo com o de Dijkstra (eficiência). As duas partes são necessárias, pois o objetivo é competir com Dijkstra e não apenas resolver o problema do caminho de custo mínimo.
Para a parte da correção, eu espero uma demonstração convincente e geralmente invariantes são o melhor jeito de se obter isso. Eu não me importo se você "reciclar" invariantes de algoritmos vistos em aula ("o invariante X do algoritmo Y do livro PF também vale para o exercício..."), mas se você for fazer isso deixe muito claro qual é o algoritmo, qual é o invariante e porque você pode "reciclá-lo". Por exemplo: se você se referir a um certo invariante a respeito do valor de uma variável Z e o algoritmo do exercício modifica Z em circunstâncias diferentes das do algoritmo visto em aula (tem um "if" a mais, o valor atribuído é diferente, etc.), então a "reciclagem" não é direta e você precisa justificar mais detalhadamente porque o invariante continua valendo.
Para a parte da eficiência, o ideal é demonstrar que o algoritmo é o(complexidade do Dijsktra).
Se sua resposta for não, a falha do algoritmo também pode estar na correção ou na eficiência. Se for na correção, você deve mostrar uma instância (ou uma família de instâncias) para a qual o algoritmo não faz o que promete. Explique pelo menos um pouco porque o algoritmo falha (uma simulação é bem-vinda) ao invés de simplesmente desenhar o grafo e não falar mais nada. Se for na eficiência, o ideal é demonstrar que o algoritmo é \omega(complexidade do Dijkstra).
Lembre-se também que a resposta pode ser "talvez": se o algoritmo estiver correto (e você provou isso) e for \Theta(complexidade do Dijkstra) (e você provou isso), ainda resta a competitividade na prática. Nesse caso a argumentação fica mais subjetiva e não existe uma resposta exata, eu apenas espero que a argumentação seja coerente.
Para a parte da correção, eu espero uma demonstração convincente e geralmente invariantes são o melhor jeito de se obter isso. Eu não me importo se você "reciclar" invariantes de algoritmos vistos em aula ("o invariante X do algoritmo Y do livro PF também vale para o exercício..."), mas se você for fazer isso deixe muito claro qual é o algoritmo, qual é o invariante e porque você pode "reciclá-lo". Por exemplo: se você se referir a um certo invariante a respeito do valor de uma variável Z e o algoritmo do exercício modifica Z em circunstâncias diferentes das do algoritmo visto em aula (tem um "if" a mais, o valor atribuído é diferente, etc.), então a "reciclagem" não é direta e você precisa justificar mais detalhadamente porque o invariante continua valendo.
Para a parte da eficiência, o ideal é demonstrar que o algoritmo é o(complexidade do Dijsktra).
Se sua resposta for não, a falha do algoritmo também pode estar na correção ou na eficiência. Se for na correção, você deve mostrar uma instância (ou uma família de instâncias) para a qual o algoritmo não faz o que promete. Explique pelo menos um pouco porque o algoritmo falha (uma simulação é bem-vinda) ao invés de simplesmente desenhar o grafo e não falar mais nada. Se for na eficiência, o ideal é demonstrar que o algoritmo é \omega(complexidade do Dijkstra).
Lembre-se também que a resposta pode ser "talvez": se o algoritmo estiver correto (e você provou isso) e for \Theta(complexidade do Dijkstra) (e você provou isso), ainda resta a competitividade na prática. Nesse caso a argumentação fica mais subjetiva e não existe uma resposta exata, eu apenas espero que a argumentação seja coerente.