Questão 67385

Um professor de Algoritmos e Estruturas de Dados está ensinando sobre algoritmos em grafos e quer que seus alunos compreendam a aplicação do Algoritmo de Dijkstra para encontrar o caminho mais curto em um grafo ponderado. Para tornar a aula mais prática e contextualizada, ele propõe um problema: "Imagine que o campus da nossa universidade é um grafo, onde os prédios são os vértices e as calçadas entre eles são as arestas. O 'peso' de cada aresta é o tempo em minutos para caminhar por aquela calçada. Precisamos desenvolver um aplicativo que, dado um prédio de origem, calcule o menor tempo para chegar a todos os outros prédios do campus." Ele apresenta a lógica central do Algoritmo de Dijkstra: "O algoritmo mantém um conjunto de vértices cujas distâncias mínimas da origem já são conhecidas. A cada passo, ele seleciona o vértice 'não visitado' que está mais próximo da origem (a 'escolha gulosa') e o adiciona ao conjunto de visitados. Em seguida, ele 'relaxa' as arestas que saem desse vértice, ou seja, verifica se o caminho recém-encontrado para seus vizinhos é mais curto do que os caminhos conhecidos anteriormente." O professor então apresenta um pequeno grafo do campus e pede aos alunos para simularem as primeiras etapas do algoritmo, partindo do vértice 'Biblioteca' (A).

Grafo: A -> B (peso 2) A -> C (peso 5) B -> C (peso 1) B -> D (peso 6) C -> D (peso 3)

Começando pela 'Biblioteca' (A), qual seria o estado das distâncias e a ordem de visita dos vértices nas duas primeiras iterações do Algoritmo de Dijkstra?