Algoritmos | Graficar las rutas más cortas | Pregunta 9

¿La siguiente afirmación es verdadera o falsa?

If we make following changes to  Dijkstra, then it can be used to find 
the longest simple path, assume that the graph is acyclic.

1) Initialize all distances as minus infinite instead of plus infinite.

2) Modify the relax condition in  Dijkstra's algorithm to update distance
  of an adjacent v of the currently considered vertex u only
  if "dist[u]+graph[u][v] > dist[v]". In shortest path algo, 
  the sign is opposite. 

(A) Verdadero
(B) Falso

Respuesta: (B)
Explicación: En el algoritmo de ruta más corta, elegimos el vértice de distancia mínima del conjunto de vértices para los cuales la distancia aún no está finalizada. Y finalizamos la distancia del vértice de distancia mínima.

Para el problema de distancia máxima, no podemos finalizar la distancia porque puede haber un camino más largo a través de vértices aún no finalizados.
Cuestionario de esta pregunta