Edición de «Final del 06/08/18 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 7: | Línea 7: | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Dados <math> G=(V,X)</math> un digrafo con pesos en sus aristas, <math>s \in V</math> y <math>k</math> un entero positivo, se quiere hallar los <math>k</math> vértices más cercanos a <math>s</math> con un algoritmo cuya complejidad sea <math>O(nk)</math>. | Dados <math>G=(V,X)</math> un digrafo con pesos en sus aristas, <math>s \in V</math> y <math>k</math> un entero positivo, se quiere hallar los <math>k</math> vértices más cercanos a <math>s</math> con un algoritmo cuya complejidad sea <math>O(nk)</math>. | ||
a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no. | a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no. |