Snowflake SnowPro Core
Get started today
Ultimate access to all questions.
Deep dive into the quiz with AI chat providers.
We prepare a focused prompt with your quiz and certificate details so each AI can offer a more tailored, in-depth explanation.
Um mapa rodoviário é modelado como um grafo em que os vértices representam interseções. As arestas representam segmentos de estrada entre interseções. O peso de cada aresta representa a distância entre interseções. Agora, considere que um motorista deseja obter o caminho mais curto entre duas cidades. Dado um mapa contendo as distâncias entre cada par de interseções adjacentes, como obter o caminho mais curto entre duas cidades?
Real Exam
Community
DDanyel
A
Caminho mais curto com destino único.
B
Caminho gerador mínimo de origem única.
C
Caminho mais curto com origem única.
D
Caminho mais curto entre todos os pares de vértices.
E
Caminho gerador mínimo de origem múltipla.
Explanation:
Explanation
This question is about finding the shortest path between two cities in a road network modeled as a weighted graph. The correct approach is C) Caminho mais curto com origem única (Single-source shortest path).
Why option C is correct:
- Single-source shortest path algorithms (like Dijkstra's algorithm) are designed to find the shortest path from a single starting vertex (source) to all other vertices in the graph.
- In this scenario, the driver wants to find the shortest path between two specific cities, which can be solved by running a single-source shortest path algorithm from the starting city and stopping when the destination city is reached.
- Algorithms like Dijkstra's algorithm are specifically designed for weighted graphs with non-negative edge weights (like distances between intersections).
Why other options are incorrect:
- A) Caminho mais curto com destino único: This translates to "single-destination shortest path," which is essentially the same as single-source shortest path but reversed. While technically equivalent, the standard terminology is "single-source."
- B) Caminho gerador mínimo de origem única: This means "minimum spanning tree from single source," which finds a tree connecting all vertices with minimum total weight, not the shortest path between two specific vertices.
- D) Caminho mais curto entre todos os pares de vértices: This is "all-pairs shortest path," which computes shortest paths between every pair of vertices (like Floyd-Warshall algorithm). This is inefficient for finding the path between just two specific cities.
- E) Caminho gerador mínimo de origem múltipla: This means "minimum spanning tree from multiple sources," which is not relevant to finding shortest paths between two specific vertices.
Key Algorithm:
Dijkstra's algorithm is the classic solution for this problem when all edge weights are non-negative (as they are with distances). It efficiently finds the shortest path from a single source to all other vertices in O((V+E) log V) time using a priority queue.
Comments
Loading comments...