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