Considere um grafo não direcionado e ponderado, re...

Q: Considere um grafo não direcionado e ponderado, representado por G = (V,E), onde V é o conjunto de vértices e E é o conjunto de arestas com pesos positivos. Você precisa encontrar o caminho mais curto

A) O algoritmo de Dijkstra, com complexidade O(E + V lg V), é o mais eficiente para grafos com pesos positivos, garantindo a solução dos caminhos mínimos a partir de um vértice s. | B) O algoritmo de Floyd-Warshall, que tem complexidade O(n3), é o mais eficiente, pois calcula os caminhos mínimos entre todos os pares de vértices. | C) O algoritmo de Kruskal, que é ideal para encontrar a árvore geradora mínima, resolve eficientemente o problema dos caminhos mais curtos com complexidade O(E lg V). | D) O algoritmo de Bellman-Ford, com complexidade O(V E), é mais eficiente para resolver o problema de caminhos mínimos em grafos com pesos positivos, pois permite a presença de ciclos. | E) O algoritmo de Prim, com complexidade O(E lg V), é ideal para encontrar caminhos mínimos em grafos ponderados, garantindo a menor soma dos pesos das arestas.

457941201336964

Ano: 2024Banca: IF-MGOrganização: IF-MGDisciplina: Estruturas de Dados e AlgoritmosTemas: Teoria dos Algoritmos | Estruturas de Dados

Considere um grafo não direcionado e ponderado, representado por G = (V,E), onde V é o conjunto de vértices e E é o conjunto de arestas com pesos positivos. Você precisa encontrar o caminho mais curto de um vértice s para todos os outros vértices do grafo. Qual dos seguintes algoritmos é mais eficiente para resolver esse problema, considerando que o grafo pode conter ciclos e as arestas possuem apenas pesos positivos?

Gabarito comentado

Anotações

Marcar para revisão

Considere um grafo não direcionado e ponderado, representado por G ...

Questões relacionadas para praticar

Considere um grafo não direcionado e ponderado, representado por G ...

Questões relacionadas para praticar