Questão para prova oral 153

Enunciado:
A Internet é composta por inúmeros computadores conectados entre si. Tais computadores estão ligados a distâncias relativamente grandes (cidades e países). Além disso, o uso de diferentes tecnologias de transmissão influencia diretamente na velocidade da comunicação.
Uma vez visto isso, podemos facilmente representá-la por um grafo não orientado. Também podemos aplicar alguns algoritmos em grafos para solucionar problemas referentes a ela. Um exemplo disso está em encontrar um caminho de custo mínimo entre dois computadores (permitindo que se comuniquem), levando em consideração distância e velocidade de transmissão.
Obs.: Para uma visualização melhor, considere os computadores como sendo os vértices e as arestas a ligação (links) entre eles.

Em qual algoritmo em grafos (visto em aula) poderiamos nos basear para solucionar o problema, tendo em vista eficiência e complexidade?

A) O algoritmo de Bellman-Ford, pois a existência de ciclos negativos deve ser considerada.
B) O algoritmo de Dijkstra, pois se encaixa perfeitamente na aplicação.
C) O algoritmo de Bellman-Ford, mas somente com o aperfeiçoamento de Yen.
D) O algoritmo DAG-SHORTEST-PATHS.
E) N.D.A.

Autor: Thiago Alves da Silva