Questão para a prova oral 154

Enunciado:
Considere um grafo orientado ponderado G = (V, E) para o qual será aplicado o algoritmo de Dijkstra, a fim de encontrar caminhos mais curtos de fonte única. Supondo que o grafo G possua arestas de peso negativo, qual o efeito no resultado obtido pelo referido algoritmo:

A) O algoritmo produzirá sempre resultados corretos, no entanto, seu tempo de execução será assintoticamente mais lento (equivalente ao de Bellman-Ford), quando comparado à sua aplicação com grafos sem arestas de peso negativo.

B) Se houver arestas de peso negativo, não será possível garantir uma propriedade fundamental do algoritmo, que o permite escolher a cada iteração da repetição principal o vértice de menor peso. Por isto, o algoritmo pode não funcionar corretamente.

C) O único problema com as arestas de peso negativo são a possibilidade de formação dos ciclos de peso negativo, os quais o algoritmo não detecta. Nos demais casos o algoritmo produz resultados corretos.

D) O algoritmo de Dijkstra possui um mecanismo de compensação, que o permite funcionar com arestas de peso negativo, convertendo-as para peso positivo e produzindo um resultado sempre correto.

E) NDA

Autor(a): André Santanchè
RA: 022287