POSCOMP 2019: Questão 36 Resolvida (Teoria dos Grafos)

Questão

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?

• (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.

Resolução

Não existe "caminho gerador mínimo" na Teoria dos Grafos, mas sim árvores geradoras mínimas e caminhos mínimos. Portanto, as alternativas B e E estão erradas.

O problema proposto deve utilizar algum algoritmo de caminho mínimo. Como o motorista deve iniciar a corrida de um ponto de partida e desse ponto traça-se as menores rotas para a cidade destino, então não faz sentido obter o menor caminho considerando apenas o destino motorista. Isso elimina a alternativa A.

A alternativa D também não faz sentido, já que queremos apenas o menor caminho dado uma origem e um destino e não entre todos os vértices possíveis.

Ou seja, a alternativa correta é a C. Nesse caso, pode-se utilizar o algoritmo de Dijkstra ou o algoritmo de Bellman-Ford. Ambos fornecem os caminhos mínimos entre um vértice de origem (local onde o motorista está) e os demais vértices dos grafo, formando uma árvore geradora mínima. Assim, basta escolher o caminho da árvore onde fica a cidade de destino.

Outra alternativa é a versão original do algoritmo de Dijkstra, que fornece o menor caminho entre dois vértices específicos, ao invés de fornecer uma árvore geradora mínima.

Contudo, a abordagem utilizando árvores de caminhos mínimos é melhor, já que uma cidade, no modelo da questão, provavelmente vai ter múltiplos vértices.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.

Referências

FEOFILOFF, P. Algoritmo de caminhos mínimos. IME-USP. Acesso em 17 de março de 2020.