Suponha um grafo onde os vértices são cidades, as arestas estradas entre cidades, e o peso das arestas corresponde a distância entre pares de cidades.

É possível, portanto, se for fornecido um valor da velocidade do veículo, usar Dijkstra para encontrar o caminho mais rápido entre 2 cidades, e obter o tempo gasto nesse caminho mínimo. Para isto, basta modificar o custo das arestas para indicar o tempo = distância / velocidade e não a distância.

Qual das seguintes variações do problema exige, para ser resolvida, modificar o algoritmo Dijkstra original, não sendo possível utilizar o Dijstra inalterado, como caixa preta, e apenas modificar o grafo de entrada, inclusive a escolha dos vértices inicial e final?

Marque a alternativa CORRETA.