Answer: Caminho mais curto com origem única.

## 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: 1. **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. 2. 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. 3. 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.

Author: Danyel Barboza