O algoritmo de Dijkstra calcula a menor distância entre dois nós em um grafo cujas arestas possuem pesos. O grafo ilustrado na figura representa um conjunto de cidades e o custo das conexões entre elas.
Considerando a aplicação do algoritmo de Dijkstra no grafo, quais das afirmações são verdadeiras?
I. A distância computada pelo algoritmo entre os nós A e B é igual a 3.
II. A distância computada pelo algoritmo entre os nós A e C é igual a 5.
III. A distância computada pelo algoritmo entre os nós A e D é igual a 4.
IV. A distância computada pelo algoritmo entre os nós A e E é igual a 5.
Apenas I é verdadeira.
II e V são verdadeiras.
III e VI são verdadeiras.
Todas são verdadeiras.
Apenas IV é verdadeira.
Considerando a aplicação do algoritmo de Dijkstra no grafo, quais das afirmações são verdadeiras?
I. A distância computada pelo algoritmo entre os nós A e B é igual a 3.
II. A distância computada pelo algoritmo entre os nós A e C é igual a 5.
III. A distância computada pelo algoritmo entre os nós A e D é igual a 4.
IV. A distância computada pelo algoritmo entre os nós A e E é igual a 5.
Apenas I é verdadeira.
II e V são verdadeiras.
III e VI são verdadeiras.
Todas são verdadeiras.
Apenas IV é verdadeira.
Lista de comentários
Resposta: Todas são verdadeiras.
Explicação: Para cada um dos nós considerados nas alternativas, devemos somar os valores das distâncias apresentadas. Mesmo que o caminho pareça sinuoso/estranho demais, o que importa é a soma final dos valores das distâncias. Algo como um exercício de percolação, que ao final nos dará a menor distância valorada entre os nós.