MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Um grupo de pesquisadores desenvolveram um módulo de navegação para robôs, usando o algoritmo de Djikstra, que soluciona o problema do caminho mais curto de única origem. Dois robôs-protótipos, construídos com as mesmas configurações de hardware, foram posicionados em salas diferentes, marcadas com as letras 'A' e 'B', de um labirinto projetado conforme o grafo abaixo. Os robôs se deslocam entre as salas do labirinto, seguindo a direção das arestas do grafo, e percorrendo uma distância equivalente ao peso dessas arestas. 

Sabendo que o robô campeão é quem chega primeiro à sala 'G' e que apenas um robô pode ser campeão, marque a alternativa correta com o percurso do robô campeão, e as respectivas estimativas de caminhos mais curtos de cada sala percorrida.

1. Robô A: A(0) → E(2) → C(4) → D(8) → G(9)
2. Robô A: A(0) → E(2) → C(6) → D(8) → G(9)
3. Robô B: B(0) → F(1) → E(2) → C(4) → D(8) → G(9)
4. Robô B: B(0) → F(1) → D(8) → G(9)
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto