Considere as informações sobre o Algoritmo de Dijkstra para resolução do problema do caminho mais curto em grafos. Assinale a alternativa correta. ...

Considere as informações sobre o Algoritmo de Dijkstra para resolução do problema do caminho mais curto em grafos. Assinale a alternativa correta.

a. O Algoritmo de Dijkstra pode ser aplicado em grafos com arestas de peso negativo, pois sempre encontrará o caminho mais curto, independentemente dos pesos.
b. O Algoritmo de Dijkstra é um exemplo de um algoritmo não guloso, pois não faz escolhas localmente ótimas.
c. A complexidade computacional do Algoritmo de Dijkstra é sempre quadrática, independentemente da implementação.
d. O Algoritmo de Dijkstra é um exemplo de um algoritmo não guloso, pois não faz escolhas localmente ótimas.
e. Uma das aplicações práticas do Algoritmo de Dijkstra é na determinação de rotas em sistemas de navegação GPS.

Pesquisa Operacional I

•

Outros

0

1

Questões Para o Saber

29/11/2023

Essa pergunta também está no material:

6 pág.

PESQUISA OPERACIONAL QUESTIONÁRIO UNIDADE II

Pesquisa Operacional I • Universidade PaulistaUniversidade Paulista

Alessandro Daniel

💡 1 Resposta

Ed

29.11.2023

A alternativa correta é a letra "e". Uma das aplicações práticas do Algoritmo de Dijkstra é na determinação de rotas em sistemas de navegação GPS. As demais alternativas estão incorretas: a. O Algoritmo de Dijkstra não pode ser aplicado em grafos com arestas de peso negativo, pois pode entrar em um loop infinito. b. O Algoritmo de Dijkstra é um exemplo de um algoritmo guloso, pois faz escolhas localmente ótimas. c. A complexidade computacional do Algoritmo de Dijkstra depende da implementação e pode ser menor que quadrática em alguns casos. d. Repetida.

0