Question

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.

Accepted Answer

E) Todas as alternativas anteriores podem ser resolvidas com o algoritmo original, se for permitido modificar a entrada, em tempo polinomial mesmo considerando a modificação da entrada. 2 Para as questões 3 e 4, considere as seguintes funções de hash em pseudo-código para gerar códigos de hash para strings.

Answer

A) Considerar que o usuário gasta um tempo extra na cidade onde começa a viagem e na cidade onde termina (sair/chegar de/em casa, des/arrumar a bagagem). É fornecida uma tabela destes tempos para cada cidade.

Answer

B) Considerar que cada estrada tem uma velocidade máxima definida e fornecida, possivelmente menor que a velocidade nominal do veículo, e que o motorista nunca ultrapassa a velocidade permitida.

Answer

C) Considerar que ao passar por uma cidade, o usuário gasta um tempo fixo e igual para todas as cidades (dado) para se locomover dentro da cidade.

Answer

D) Considerar que ao passar por uma cidade, o usuário gasta um tempo predeterminado para se locomover dentro da cidade que varia de acordo com as estradas de chegada e de partida da cidade. Por exemplo, tabulamos um tempo gasto por quem chega em São José dos Campos pela Rodovia Dutra e parte pela Rodovia Tamoios, e outro tempo para quem chega pela Tamoios e parte pela Rodovia Monteiro Lobato. Para cada cidade, é dada uma matriz onde linhas e colunas são todas as estradas que incidem sobre a cidade, e os elementos são o tempo gasto para se deslocar dentro da cidade entre uma estrada e outra.

Mais questões de Árvores e grafos