Questão de Análise de Sistemas · CESGRANRIO BNDES 01/2024 (nº 50)

Conceito-chave: O problema pede a menor distância entre dois pontos em um grafo (mapa de ruas). O algoritmo de Dijkstra resolve exatamente isso: ele parte do ponto inicial e vai "abrindo" as rotas mais curtas conhecidas, atualizando as distâncias até chegar ao destino final.

• (A) Incorreta: Bubblesort é um algoritmo de ordenação de listas (ex: números), não serve para calcular rotas ou caminhos em mapas.
• (B) Correta: Dijkstra é o algoritmo clássico de caminho mínimo em grafos com pesos não negativos (distâncias), exatamente o que o software precisa para achar a rota mais curta entre os pontos inicial e final.
• (C) Incorreta: Ford-Fulkerson é usado para calcular fluxo máximo em redes (ex: fluxo de água em canos), não para achar a menor distância entre dois pontos.
• (D) Incorreta: Kruskal encontra a árvore geradora mínima (conecta todos os pontos com o menor custo total), mas não calcula a distância entre dois pontos específicos.
• (E) Incorreta: Quicksort é outro algoritmo de ordenação (mais rápido que o Bubblesort), sem relação com grafos ou rotas.

Armadilha da banca: O distrator mais tentador é Kruskal (D), pois também trabalha com "menor custo" em grafos. A pegadinha é que Kruskal minimiza o custo para conectar todos os pontos (criando uma árvore), enquanto o problema pede a distância entre dois pontos específicos — isso é função do Dijkstra.