Algoritmos y Estructuras de Datos (VJ1215)

El coste temporal del algoritmo del ejercicio 26 es O(|E| + |V|).

El coste temporal del algoritmo de Dijkstra depende de cómo se implementa la cola de prioridad (ejercicio 14 del tema 6 y ejercicio 29 del tema 1). Por ejemplo, es O(|E| + |V| log |V|) si la cola de prioridad se implementa con monticulos de Fibonacci.

En cualquier caso, el algoritmo del ejercicio 26 es más eficiente que el algoritmo de Dijkstra. Pero ambos algoritmos tienen requisitos diferentes. El algoritmo de Dijkstra requiere que el grafo no tenga arcos de peso negativo. El algoritmo del ejercicio 26 no tiene ese requisito, pero requiere que el grafo sea acíclico.