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

En un grafo conectado no dirigido y no ponderado, la ruta más corta desde un Node S a todos los demás Nodes se calcula de manera más eficiente, en términos de complejidad de tiempo, mediante
(A) el algoritmo de Dijkstra a partir de S.
(B) el algoritmo de Warshall
(C) Realización de un DFS a partir de S.
(D) Realización de un BFS a partir de S.

Respuesta: (D)
Explicación:

 * Time Complexity of the Dijkstra’s algorithm is O(|V|^2 + E)  
 * Time Complexity of the Warshall’s algorithm is O(|V|^3)
 * DFS cannot be used for finding shortest paths
 * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

Cuestionario de esta pregunta