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

¿Cuál es la complejidad temporal del algoritmo de ruta más corta de fuente única de Bellman-Ford en un gráfico completo de n vértices?

(A) $\Theta(n^2)$
(B) $\Theta(n^2 Logn)$
(C) $\Theta(n^3)$
(D) $\Theta(n^3 Logn)$

Respuesta: (C)
Explicación: La complejidad temporal del algoritmo de Bellman-Ford es $\Theta(VE)$ donde V es el número de vértices y E es el número de aristas (ver esto ). Si la gráfica está completa, el valor de E se convierte en $\Theta(V^2)$ . Entonces, la complejidad del tiempo general se convierte $\Theta(V^3)$
en el 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

Deja una respuesta Cancelar la respuesta