Caminho mínimo em grafo: o erro de confundir trechos, cidades e pesos

Eu costumo perceber que a turma ainda não entendeu caminho mínimo quando apresento um mapa simples e alguém escolhe a rota que parece mais direta no desenho. O aluno aponta para a linha visualmente curta, mas não confere se cada conexão existe, se as setas permitem aquele percurso ou quantos trechos realmente percorreu. Em outra situação, ele chega ao destino, porém conta as cidades visitadas como se fossem estradas. Não é falta de atenção pura e simples: muitas vezes, a representação ainda não está clara e a palavra “menor” parece ter apenas um significado.

Também já vi estudantes escolherem um trajeto com poucas ligações mesmo quando o problema pergunta pelo menor tempo, ou defenderem uma busca em profundidade porque ela “vai direto” ao destino. Para mim, esses erros são pistas úteis. Eles mostram se preciso retomar leitura de grafo, direção das arestas, contagem de etapas, pesos ou propriedades dos algoritmos. O caminho mínimo rende uma boa conversa matemática e computacional justamente porque obriga a turma a explicitar o critério de otimização, em vez de confiar na aparência do desenho.

O que é caminho mínimo em grafo, explicado para o professor

Caminho mínimo é um percurso entre um vértice de origem e um vértice de destino que minimiza um critério definido. Em um grafo sem pesos, esse critério costuma ser o número de arestas: se cada ligação vale uma etapa, procuramos chegar ao destino usando o menor número de ligações. Em um grafo ponderado, cada aresta recebe um valor, como distância, duração ou custo, e o objetivo pode ser minimizar a soma desses pesos. É importante dizer qual dos dois problemas está em jogo: o caminho com menos arestas nem sempre tem o menor peso total. O conceito aparece em Matemática e Computação em situações como trajetos entre cidades, conexões entre salas, ruas entre bairros, rotas de drones e busca de caminhos livres em jogos. Nas questões consideradas aqui, ele aparece do 5º ao 9º ano, com habilidades associadas a EF05CO02, EF06MA34, EF07CO04, EF08CO04 e EF09CO01.

Para concretizar, imagine as ligações A–B, A–C, B–D, C–D e D–E. Se todas valem uma etapa, basta comparar sequências válidas e contar arestas. Já quando cada ligação tem um tempo diferente, somamos os tempos. Um trajeto de duas arestas pode custar mais do que outro de três. Eu procuro separar essas perguntas no quadro: “qual tem menos ligações?” e “qual tem menor soma de custos?”. Essa distinção impede que a turma trate caminho mínimo como uma única receita. Também ajuda a explicar por que BFS é apropriada para encontrar menos arestas em grafo não ponderado, enquanto Dijkstra pode encontrar menores distâncias a partir de uma fonte quando os pesos são não negativos.

O que o aluno precisa saber antes de estudar caminho mínimo?

As fichas das oito questões apontam pré-requisitos que vão da leitura de grafos simples às propriedades de algoritmos. A turma precisa reconhecer vértices e arestas, interpretar uma lista de adjacência ou um fluxograma, distinguir conexões direcionadas e não direcionadas, seguir a orientação das setas e compreender o que significa um percurso válido. Nos itens mais algorítmicos, entram busca em grafos, BFS e DFS, pesos, algoritmos de grafos e estruturas de dados; em um item, também é necessário pensar em parâmetros e reutilização de resultados entre várias instâncias. Para verificar a base, eu mostro um grafo pequeno sem perguntar ainda pelo menor caminho: peço que os alunos indiquem as conexões existentes, enumerem dois percursos possíveis e expliquem se uma ligação pode ser percorrida nos dois sentidos. Assim, separo dificuldade de leitura da representação de dificuldade de otimização.

Uma verificação rápida pode ser feita em cinco minutos, oralmente ou em uma folha: “Existe uma aresta direta entre A e D?”, “A→B→D é permitido neste grafo dirigido?”, “Quantas arestas há nesse percurso?” e “O que muda se cada aresta tiver um peso?”. Eu observo não apenas a resposta, mas a justificativa. Se o estudante inventa uma ligação porque ela parece natural no mapa, retomo representação; se ignora uma seta, retomo direção; se conta vértices, modelo a diferença entre pontos e trechos. Se sabe validar percursos, mas não consegue comparar custos, avanço para pesos. Essa sondagem inicial evita apresentar Dijkstra a quem ainda não interpreta as conexões e ajuda a escolher entre uma atividade concreta, uma explicação visual ou uma tarefa de algoritmo.

Quais são os erros mais comuns ao resolver caminho mínimo?

Nas oito fichas, os erros descritos não são todos iguais: alguns envolvem a escolha de um percurso que não minimiza paradas; outros, a validade das conexões, a direção das setas, a contagem de arestas ou a diferença entre pesos e quantidade de arestas. Há ainda confusões entre BFS e DFS e entre algoritmos destinados a problemas diferentes. Não é correto dizer que um único erro se repete em todas as questões. O padrão pedagógico mais útil é outro: o aluno pode chegar a uma sequência plausível sem ter aplicado o critério pedido. Os distratores mais prováveis variam conforme o item — A aparece nas questões 1, 3, 5 e 8; B, na 2; C, na 4; e E, na 6. Eu uso a alternativa escolhida como hipótese sobre o raciocínio, não como diagnóstico definitivo, e peço ao estudante que explique o caminho passo a passo.

Escolher um percurso válido, mas que não é o menor

Na questão das cidades Solar, Aurora, Brisa, Coral e Diamante, vários trajetos chegam ao destino, mas só se minimiza comparando o número de estradas. O distrator A, Solar–Aurora–Brisa–Diamante, é um percurso possível, porém usa mais arestas do que Solar–Brisa–Diamante. Esse tipo de escolha sugere que o aluno reconhece conexões, mas ainda não compara sistematicamente o critério. Eu intervenho pedindo que liste todas as alternativas válidas e registre ao lado quantas arestas cada uma percorre. Essa tabela torna a otimização visível sem transformar a tarefa em cálculo.

Confundir desenho atraente com conexão existente

Na questão das salas A, B, C e D, A–C–D parece uma resposta curta, mas a ligação C–D não foi informada. O distrator A revela que o estudante pode completar mentalmente o desenho ou supor uma aresta. A dica da ficha é desenhar o grafo para visualizar as conexões. Eu reforço uma regra simples: só percorremos uma aresta se ela estiver indicada no enunciado ou na representação. Depois peço que o aluno marque cada ligação usada na rota. Se não consegue marcar uma delas, o percurso não é válido, ainda que pareça intuitivo.

Ignorar a direção das setas ou contar vértices como trechos

No fluxograma dos municípios A, B, C, D e E, as ligações têm direção. É preciso seguir as setas, e o menor caminho tem três trechos; quatro cidades visitadas não significam quatro trechos. A ficha identifica como erros contar trechos inexistentes, desrespeitar a direção e confundir trechos com cidades. Eu desenho setas grandes e peço que a turma narre o percurso como uma sequência de movimentos permitidos. Depois pergunto quantas setas foram percorridas. Essa intervenção diferencia vértices, que representam lugares, de arestas, que representam conexões.

Acreditar que DFS garante o menor número de arestas

O distrator A da questão sobre BFS e DFS atribui à busca em profundidade uma garantia que ela não oferece. A DFS pode seguir um ramo longo antes de encontrar o destino; evitar ciclos não faz com que explore por níveis. A causa provável é confundir “encontrar um caminho” com “encontrar o menor”. Eu comparo as duas estratégias em um grafo pequeno: na BFS, exploro primeiro todos os vértices a uma aresta da origem, depois os que estão a duas, e assim por diante. Peço aos alunos que identifiquem em qual ordem o destino é encontrado e justifiquem a garantia apenas para grafos não ponderados.

Tratar menos arestas como sinônimo de menor peso

Na questão sobre tempos de tráfego, o caminho de menor peso é preferível quando queremos minimizar o tempo total representado pelos pesos. O distrator C sugere que o aluno pode acreditar que pesos iguais justificam escolher esse critério, embora, se todos forem iguais, minimizar o peso e minimizar a quantidade de arestas coincidam. O erro central descrito na ficha é comparar número de ligações em vez da soma dos pesos. Eu uso dois percursos com valores explícitos e peço primeiro a contagem de arestas, depois a soma. Assim a turma vê que são perguntas distintas, mesmo quando uma situação concreta — como tempo de viagem — dá sentido aos pesos.

Reduzir uma solução para várias instâncias a um único par

Na assinatura do algoritmo em lote, o distrator B considera apenas um parâmetro de origem e destino. O enunciado, porém, pede várias instâncias e uma estrutura que possa ser reutilizada. A ficha aponta a confusão entre a necessidade de parâmetros genéricos e uma solução simples demais, além de recomendar revisão de algoritmos de grafos e estruturas de dados. Eu separo a pergunta em duas: quais dados mudam entre instâncias e quais resultados podem ser reaproveitados? O objetivo não é exigir uma implementação completa de alunos iniciantes, mas verificar se percebem que grafo e pares de consulta precisam estar representados e que resultados prévios podem evitar recomputações.

Confundir Dijkstra com outros algoritmos de caminho mínimo

Na situação do drone, a ficha descreve como erro típico confundir Dijkstra com Floyd–Warshall, que calcula caminhos entre todos os pares, embora o problema peça caminhos a partir de uma base. O distrator C, A*, também pode atrair quem reconhece um algoritmo conhecido sem conferir se dispõe da heurística necessária. Eu conduzo a escolha com três perguntas: os pesos são não negativos? A consulta parte de uma fonte ou envolve todos os pares? Há uma heurística adequada disponível? Para uma fonte e pesos positivos, Dijkstra é a opção indicada no item; BFS não considera pesos, e Floyd–Warshall resolve um escopo diferente.

Achar que desenhar ou alterar o grafo garante passagem livre

Na questão do jogo, o erro típico é escolher “desenhar manualmente” como garantia de que um jogador consegue ir de A a B sem obstáculos. O desenho pode ajudar a visualizar, mas não prova conectividade nem verifica automaticamente uma rota. A ficha recomenda considerar as propriedades dos grafos e algoritmos de busca. Eu peço que a turma transforme o cenário em vértices, arestas disponíveis e obstáculos, e depois formule uma busca que verifique se B é alcançável a partir de A. O aluno precisa distinguir representar o problema de resolvê-lo: uma imagem bonita não substitui um procedimento de verificação.

Como ensinar caminho mínimo passo a passo?

Eu começo por um grafo pequeno e concreto, sem pesos, e peço que a turma marque todas as ligações antes de procurar um caminho. A primeira meta é validar: cada passo deve usar uma aresta existente e, em grafos direcionados, respeitar a seta. Em seguida, comparo rotas e conto arestas, destacando que o número de vértices visitados é um a mais quando o percurso não repete vértices. Só depois introduzo a palavra “mínimo” como comparação entre alternativas válidas. As dicas das fichas orientam essa sequência: desenhar a representação, analisar conexões e escolher a rota com menos paradas; seguir as setas; comparar BFS e DFS; e, em grafos com custos, observar os pesos. A cada etapa, peço justificativa curta para localizar exatamente a dificuldade.

Na segunda etapa, diferencio busca e otimização com uma exploração por níveis. A turma acompanha uma BFS em um grafo não ponderado, registra a distância em arestas a partir da origem e observa por que a primeira visita ao destino ocorre com o menor número de arestas. Faço uma DFS no mesmo grafo e mostro que ela pode encontrar um percurso, mas não oferece a mesma garantia. Depois acrescento pesos e proponho uma situação de tempo ou distância: cada equipe soma os custos de duas rotas. Para avançar ao algoritmo, apresento Dijkstra apenas no contexto adequado, com pesos não negativos e uma origem. Em turmas mais avançadas, discuto consultas repetidas, parâmetros e reutilização de tabela de distâncias ou árvores de caminhos por fonte, sem antecipar detalhes que a turma ainda não domina.

Como avaliar: que tipo de questão usar em cada momento?

Para diagnóstico inicial, prefiro um grafo curto, leitura média e sem cálculo, como os itens de percurso cotidiano: eles permitem observar representação, direção e contagem sem misturar muitas demandas. Nas fichas, sete questões têm tempo de resolução médio e uma, sobre várias instâncias e estrutura reutilizável, é longa; sete têm nível de leitura médio e essa mesma questão tem leitura alta. Se a intenção é avaliar algoritmos, escolho itens de discriminação alta, como BFS versus DFS, escolha de Dijkstra ou desenho de uma solução genérica. Os itens de progressão ajudam a acompanhar a construção do conceito; um item de consolidação pode fechar uma sequência; e os desafios discriminam quem já articula conceitos. A ficha indica que todas servem para prova, atividade e diagnóstico, nenhuma é marcada para avaliação rápida, e só a questão 6 é indicada para lição de casa.

Eu distribuo as questões conforme o momento, não como uma lista indiscriminada. Em atividade, peço que duplas desenhem o grafo e anotem as alternativas válidas. Em prova, combino um item de leitura de caminho com outro que exija justificar o algoritmo ou distinguir peso de número de arestas. Em simulado, sete questões estão marcadas como adequadas; a questão 8 não está. Para uma lição de casa, a ficha recomenda especificamente a questão 6, sem que isso impeça o professor de criar outra tarefa adequada. Como todas as fichas marcam “não” para avaliação rápida, eu não trataria esses itens completos como instrumentos de poucos minutos sem adaptação. As classificações de poder de discriminação variam entre médio e alto: uso as de alto poder quando quero separar níveis de compreensão, e analiso sempre a justificativa junto da alternativa escolhida.

O que ensinar antes de caminho mínimo em grafos?

As fichas apontam conhecimentos prévios específicos: interpretação de grafos simples, representação de grafos, caminhos, grafos direcionados, pesos, algoritmos de grafos, algoritmos de busca em grafos, listas de adjacência e estruturas de dados. Em turmas que já estudam programação, retomo também algoritmo de busca, representação de grafos e estruturas de dados. Para os itens interpretativos, a leitura cuidadosa do enunciado é parte do trabalho; quando a narrativa é literária, pode ser útil revisar interpretação de texto literário, sem presumir que todo item de grafo seja um texto literário. Também convém revisar algoritmo de grafo e algoritmo de busca em grafos antes de cobrar a escolha entre BFS, DFS, Dijkstra ou Floyd–Warshall.

Eu não ensino todos esses tópicos como uma lista obrigatória antes de qualquer introdução. Para uma atividade de 5º ou 6º ano, basta começar com vértices, conexões e percursos em uma representação clara. Para discutir BFS e DFS, os alunos precisam entender o que significa explorar um grafo e acompanhar uma ordem de visita. Para trabalhar a questão de lote, são necessários algoritmos de grafos e estruturas de dados, além de pensar nos parâmetros. Para pesos, a turma deve interpretar o valor associado a cada aresta e somar os custos do percurso. Faço uma checagem breve de cada pré-requisito e seleciono a revisão necessária, em vez de interromper uma sequência inteira para recapitular conteúdos que a maioria já domina.

Que relações caminho mínimo tem com outros temas?

Os contextos das fichas incluem cotidiano — cidades, ruas e salas —, cenários abstratos e situações científicas ou tecnológicas, como tráfego, drones e jogos. Isso permite relacionar o conceito a mobilidade, redes, planejamento e tecnologia, sem confundir a situação contextual com a habilidade matemática ou computacional avaliada. A ficha da questão 2 identifica ciência e tecnologia como tema transversal; a questão 3 também traz esse tema, assim como as questões 5 e 7. Nas fichas em que esse campo não aparece, não atribuo outro tema por conta própria. Em sala, posso pedir que os alunos comparem um trajeto de menor distância, menor tempo e menor número de conexões, e discutam por que a escolha depende do objetivo. Esse contraste dá propósito aos pesos e mostra que um algoritmo responde a um modelo e a um critério definidos.

As habilidades socioemocionais registradas incluem pensamento crítico nas questões 1, 2, 3, 4, 7 e 8, e tomada de decisão nas questões 5 e 6. Eu as trabalho por meio da justificativa: o estudante precisa defender por que um percurso é válido e por que atende ao critério, além de revisar a decisão diante de uma evidência melhor. Em duplas, uma pessoa pode propor a rota e a outra verificar arestas, direções e custos; depois, trocam os papéis. Não avalio pensamento crítico pela concordância com a resposta, mas pela capacidade de comparar alternativas e explicar o critério. Para criar avaliações que combinem esses contextos com objetivos claros, posso usar o gerador de provas do GeraProva e adaptar as questões à turma.

Quais questões comentadas ajudam a diagnosticar caminho mínimo?

As oito questões abaixo percorrem níveis diferentes: leitura de percursos, contagem de arestas, busca em grafo não ponderado, comparação com pesos e escolha de algoritmos. Em cada uma, a alternativa correta é indicada com ✅; nas incorretas, explico o problema e o tipo de raciocínio que a escolha pode revelar. Vale lembrar que uma alternativa isolada não prova a causa do erro: peça ao aluno que justifique e compare a resposta com sua leitura do grafo. As fichas técnicas completas ficam vinculadas a cada questão pelo marcador solicitado, sem reproduzir aqui informações adicionais que possam ser confundidas com o enunciado ou com a explicação do gabarito. Use os itens para abrir uma discussão diagnóstica, retomar conceitos ou compor uma avaliação alinhada ao que a turma já estudou.

1. Qual sequência de cidades minimiza as paradas de Solar até Diamante?

As conexões são direcionadas: Solar→Aurora, Solar→Brisa, Aurora→Brisa, Aurora→Coral, Brisa→Coral, Brisa→Diamante e Coral→Diamante. Não há estradas de retorno. Qual sequência chega a Diamante com o menor número de paradas, sem repetir cidades?

• ❌ A) Solar, Aurora, Brisa e Diamante. É válido, mas usa três estradas. Escolhê-la pode revelar que o aluno encontra uma rota possível sem comparar o número de etapas.
• ✅ B) Solar, Brisa e Diamante. Usa duas estradas, menos do que as outras rotas válidas apresentadas.
• ❌ C) Solar, Aurora, Coral e Diamante. Também usa três estradas; o erro pode ser não contar e comparar as ligações.
• ❌ D) Solar, Aurora, Brisa, Coral e Diamante. Percorre quatro estradas e não minimiza as paradas.
• ❌ E) Solar, Brisa, Coral e Diamante. É válido, mas tem três estradas; pode indicar foco na validade, sem análise do mínimo.

Gabarito comentado: Solar→Brisa→Diamante percorre duas arestas. Para diagnosticar, peça que o estudante conte estradas, não apenas cidades, em cada opção.

2. Que parâmetros e estrutura tornam genérico um algoritmo para várias consultas de caminho mínimo?

Considere um algoritmo que recebe um grafo e uma lista de pares (origem, destino). Qual proposta permite tratar instâncias diferentes e reaproveitar trabalho para melhorar o desempenho?

• ❌ A) caminhos_em_lote(grafo). Faltam os pares que definem as consultas; a escolha pode revelar que o aluno não identificou todos os dados de entrada.
• ❌ B) Usar apenas um parâmetro de origem/destino. Não representa o grafo e a lista de consultas como o problema pede; pode indicar dificuldade em decompor a interface do algoritmo.
• ❌ C) caminhos_em_lote(grafo, pares, lista_pesos). A lista de pesos, sozinha, não cumpre o papel de estratégia opcional nem resolve a necessidade de flexibilidade descrita.
• ✅ D) caminhos_em_lote(grafo, pares, heurística_opcional), com grafo, pares e estratégia ou limitações; reutilizar tabela de distâncias pré-computada ou árvore de caminhos por fonte (cache de SSSP) pode evitar recomputações.
• ❌ E) Não definir estrutura reutilizável. Ignora a possibilidade de reaproveitar resultados entre instâncias; pode revelar que o aluno pensa só na correção de uma consulta, não no desempenho em lote.

Gabarito comentado: A solução deve receber o grafo e as consultas e considerar uma estratégia reutilizável, como cache por fonte. O foco diagnóstico é reconhecer entradas e reaproveitamento.

3. Em um grafo não direcionado e não ponderado, qual busca encontra menos arestas entre dois vértices?

O grafo de ruas entre bairros está representado por lista de adjacência. Qual algoritmo é mais adequado para encontrar o caminho com menor número de arestas entre dois vértices, e por quê?

• ❌ A) DFS, porque explora profundamente e encontra primeiro o destino. A primeira rota encontrada pode ser longa; escolher isso revela confusão entre encontrar um caminho e garantir o mínimo.
• ❌ B) Busca gulosa por heurística local. Uma escolha local não garante o ótimo global; a resposta pode mostrar confiança excessiva em uma regra intuitiva.
• ❌ C) DFS com poda de ciclos. Evitar ciclos não faz a busca explorar por níveis nem garante menor quantidade de arestas; o aluno pode confundir caminho simples com caminho mínimo.
• ✅ D) BFS. Explora por níveis e encontra o destino com o menor número de arestas em grafo não ponderado.
• ❌ E) Prim. Constrói uma árvore geradora mínima, não é o algoritmo indicado para essa consulta de menor caminho entre dois vértices.

Gabarito comentado: BFS é a escolha porque visita primeiro os vértices a uma aresta, depois a duas, e assim por diante. Peça ao aluno que explique a garantia, não apenas nomeie o algoritmo.

4. Quando o caminho de menor peso é preferível ao que tem menos arestas?

Uma empresa usa dados de tráfego para escolher rotas. Em qual situação é preferível minimizar a soma dos pesos das arestas, em vez de simplesmente minimizar o número de conexões?

• ❌ A) Quando se busca o caminho com mais vértices para aumentar cobertura. Isso não expressa minimização do peso; a escolha pode indicar que o aluno não identificou o objetivo.
• ❌ B) Sempre que o grafo é direcionado. A direção define quais movimentos são permitidos, não qual critério de custo deve ser minimizado.
• ❌ C) Quando todas as arestas têm peso igual. Nesse caso, os critérios coincidem; não é uma razão para preferir menor peso a menor número de arestas.
• ✅ D) Quando as arestas representam tempos variados e queremos minimizar o tempo total.
• ❌ E) Somente em grafos muito grandes. A escolha depende do significado dos pesos e do objetivo, não apenas do tamanho do grafo.

Gabarito comentado: Se os pesos representam tempo, somamos os tempos da rota e minimizamos o total. O erro pode revelar que o estudante trata “menor” como quantidade de arestas em qualquer situação.

5. Qual é o caminho mais curto de A até D no grafo das salas?

A sala A está conectada a B e C, e B está conectada a D. Considerando somente as ligações informadas, qual caminho leva de A até D com menos arestas?

• ❌ A) A→C→D. Não existe ligação C–D no enunciado; pode revelar que o aluno supõe conexões que não foram dadas.
• ✅ B) A→B→D. As duas ligações existem e levam ao destino em duas arestas.
• ❌ C) A→B→C. O percurso não chega a D; a escolha sugere que o aluno não verificou o destino final.
• ❌ D) A→C→B→D. Não há indicação de ligação C–B, e a rota proposta seria mais longa; pode haver dificuldade em conferir as arestas.
• ❌ E) A→D. Não existe ligação direta; pode indicar que a aparência de uma rota curta se sobrepôs à representação.

Gabarito comentado: A→B→D é válido e tem duas arestas. Desenhar o grafo ajuda a conferir tanto a existência das conexões quanto a chegada ao destino.

6. Quantos trechos são necessários no menor percurso de A até E?

As setas indicam A→B, A→C, B→D, C→D e D→E. Não há trechos diretos de A para D ou E. Qual é o menor número de trechos rodoviários entre A e E?

• ❌ A) 1 trecho. Não há estrada direta de A a E; a escolha pode revelar que o aluno não seguiu as conexões.
• ❌ B) 5 trechos. O fluxograma não apresenta um percurso desse tamanho; pode indicar contagem sem apoio na representação.
• ✅ C) 3 trechos. Tanto A→B→D→E quanto A→C→D→E têm três arestas.
• ❌ D) 4 trechos. Esse valor pode surgir da confusão entre quatro cidades visitadas e três segmentos percorridos.
• ❌ E) 2 trechos. Não é possível chegar a E em dois movimentos, pois D→E é necessário e A ainda precisa chegar a D.

Gabarito comentado: O mínimo é três trechos. Peça que a turma siga as setas e conte as arestas, diferenciando-as dos quatro vértices do percurso.

7. Qual algoritmo é adequado para a rota de menor tempo de um drone?

Um drone precisa calcular a rota de menor tempo a partir de sua base em um grafo cujas arestas têm pesos positivos, representando o tempo de voo. Qual algoritmo é mais adequado?

• ✅ A) Dijkstra. Encontra caminhos mínimos a partir de uma origem em grafos com pesos não negativos.
• ❌ B) BFS. Não considera os diferentes pesos; a escolha pode mostrar que o aluno aplica a busca sem conferir o custo das arestas.
• ❌ C) A*. Pode ser adequado se houver uma heurística admissível, mas essa condição não foi fornecida; pode indicar que o aluno escolhe pelo nome sem verificar os dados.
• ❌ D) Floyd–Warshall. Calcula caminhos entre todos os pares e é mais custoso quando só se precisa de uma fonte; a ficha aponta possível confusão de escopo.
• ❌ E) Bellman–Ford. Também lida com pesos negativos, mas é mais lento que Dijkstra para pesos positivos neste contexto.

Gabarito comentado: Dijkstra corresponde a uma fonte e pesos positivos. Antes de escolher, identifique o tipo de peso e se a consulta é de uma origem ou de todos os pares.

8. Como verificar se um jogador consegue ir de A a B sem obstáculos?

Em um jogo, os personagens e os caminhos disponíveis são representados por um grafo. Qual estratégia pode verificar se o jogador consegue chegar de A a B sem passar por obstáculos?

• ❌ A) Desenhar o gráfico manualmente. A representação pode ajudar, mas não garante que exista um caminho livre; a escolha pode revelar confusão entre visualizar e verificar.
• ✅ B) Usar um algoritmo de busca. Ele pode percorrer as conexões disponíveis e identificar se B é alcançável a partir de A.
• ❌ C) Adicionar mais personagens. Isso não verifica nem garante uma conexão livre entre os pontos.
• ❌ D) Limitar o número de arestas. Pode eliminar caminhos viáveis sem demonstrar que existe uma rota.
• ❌ E) Criar obstáculos aleatórios. Isso dificulta a passagem, em vez de verificar um caminho sem obstáculos.

Gabarito comentado: Uma busca permite verificar a alcançabilidade considerando as conexões disponíveis. A turma deve distinguir a representação do cenário do procedimento que testa a existência do caminho.

Quais dúvidas frequentes aparecem ao ensinar caminho mínimo?

As dúvidas mais comuns tratam da diferença entre caminho e caminho mínimo, da escolha entre BFS e Dijkstra, da necessidade de desenhar o grafo e da forma de interpretar pesos e direções. Minha recomendação é sempre voltar ao enunciado antes de selecionar um algoritmo: qual é a origem, qual é o destino, que conexões existem e o que significa “menor” naquele problema? Essa leitura evita aplicar uma técnica correta ao objetivo errado. Também vale aceitar mais de uma rota quando há empate e pedir que o aluno demonstre que ela atende ao critério. O conceito fica mais compreensível quando a avaliação considera processo e justificativa, não apenas a alternativa marcada.

Caminho mínimo sempre significa passar por menos cidades?

Não. Em geral, o critério pode ser menor número de arestas ou menor soma dos pesos, conforme o enunciado. O número de cidades visitadas se relaciona ao de arestas, mas não é o mesmo: em um caminho sem repetição, há uma cidade a mais do que trechos. Em um grafo ponderado, uma rota com mais arestas pode ter menor custo total.

BFS sempre encontra o caminho mais curto?

BFS encontra um caminho com o menor número de arestas em grafos não ponderados, ou quando todas as arestas têm o mesmo peso. Se os pesos representam custos diferentes, a quantidade de arestas não basta para decidir; é preciso um algoritmo adequado ao problema ponderado, como Dijkstra para pesos não negativos e uma origem.

Qual é a diferença entre BFS, DFS e Dijkstra?

BFS explora por níveis e garante o menor número de arestas em grafo não ponderado. DFS aprofunda um percurso e pode encontrar uma solução, mas não garante que ela tenha menos arestas. Dijkstra considera pesos não negativos para encontrar menores custos a partir de uma origem. A escolha depende da representação e do critério pedido.

Como diagnostico se o erro está na leitura ou no algoritmo?

Peça que o aluno desenhe ou leia as conexões, marque as arestas usadas, siga as setas e conte os trechos antes de nomear um algoritmo. Se não valida a rota, retome representação e direção. Se valida rotas, mas não sabe comparar quantidades, trabalhe o critério. Se entende o objetivo, mas escolhe DFS para garantir mínimo ou confunde Dijkstra com Floyd–Warshall, retome as propriedades dos algoritmos.

Posso ensinar caminho mínimo sem programação?

Sim. É possível começar com mapas, fluxogramas e grafos desenhados, comparando percursos e contando arestas. Essa abordagem permite construir o conceito antes de implementar BFS ou Dijkstra. Em Computação, a programação pode entrar depois para automatizar a busca e discutir eficiência; em Matemática, a representação e a justificativa já permitem explorar o problema.

Como adaptar as questões para uma turma com níveis diferentes?

Comece por grafos pequenos, linguagem direta e conexões explícitas para verificar compreensão básica. Depois varie uma exigência de cada vez: direção, número de alternativas, pesos ou escolha de algoritmo. As fichas apontam leitura média para sete itens e alta para a questão de lote; essa última pode exigir mediação ou preparação. Para organizar uma avaliação adequada ao seu planejamento, faça o cadastro grátis no GeraProva.

Se quiser transformar esses diagnósticos em uma sequência de atividades alinhada ao que sua turma já sabe, experimente o GeraProva e adapte as questões ao seu contexto. Um bom caminho começa por identificar qual conexão conceitual ainda falta.