Suponha que quer encontrar o caminho mais curto (de menor custo) num grafo com as características do grafo apresentado abaixo, mas que pode ter muitos mais nós e arcos.

Indique qual a opção correta em relação ao(s) algoritmos que deve escolher.

Question

Suponha que quer encontrar o caminho mais curto (de menor custo) num grafo com as características do grafo apresentado abaixo, mas que pode ter muitos mais nós e arcos. 
 
 Indique qual a opção correta em relação ao(s) algoritmos que deve escolher.

Answer

Podemos usar tanto o algoritmo adaptado para DAGs (com ordenação 
topológica) quanto o Bellman-Ford, mas o algoritmo Bellman-Ford 
será consideravelmente mais rápido.

Answer

Podemos usar apenas o  BFS .

Answer

Podemos usar apenas o algoritmo de Dijkstra, pois o grafo não é um DAG e não possui pesos negativos.

Answer

Nenhum dos algoritmos podem ser utilizados pois o grafo possui um ciclo com a soma dos pesos negativos.

Answer

Quaisquer dos algoritmos entre o Dijkstra, o algoritmo adaptado para DAGs (com ordenação topológica) e o Bellman-Ford podem ser usados, mas o algoritmo adaptado para DAGs será consideravelmente mais rápido.

Crowdly

Suponha que quer encontrar o caminho mais curto (de menor custo) num grafo com a...

Want instant access to all verified answers on moodle24.iscte-iul.pt?