MO417 - Questão para a prova oral

Número: 2003-154

Enunciado: Considere um grafo orientado ponderado G = (V, E) sobre o qual será aplicado o algoritmo de Dijkstra para 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

Ideia original de: André Santanchè