Para implementar el algoritmo de ruta más corta de Dijkstra en gráficos no ponderados para que se ejecute en tiempo lineal, la estructura de datos que se utilizará es:
(A) Cola
(B) Pila
(C) Heap
(D) B-Tree
Respuesta: (A)
Explicación: La ruta más corta en un gráfico no ponderado significa el menor número de aristas que deben atravesarse para llegar al destino en el gráfico. Este es el mismo problema que resolver la versión ponderada donde todos los pesos son 1. Si usamos Queue (FIFO) en lugar de Priority Queue (Min Heap), obtenemos la ruta más corta en tiempo lineal O(|V| + | E|). Básicamente, hacemos un recorrido BFS del gráfico para obtener los caminos más cortos.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA