Algoritmos para grafos (C)

[Valkyr]

Eso es falso, el orden de complejidad de Dijkstra es mayor que el de BFS y a la práctica también es más lento

El algoritmo de Dijkstra es un algoritmo voraz (avance rápido) y tiene un orden de complejidad de O(n²), incluso se puede conseguir un O(a·log n) siendo a el número de aristas haciendo una implementación distinta a la que se suele usar. Y los algoritmos de BFS (al menos, los que yo he visto) tienen un orden de O(n²) con matrices de adyacencia, y O(a+n) con listas de adyacencia. Así que tampoco se diferencian tanto los tiempos de ejecución cuando tienes un grafo completo.

[ghastlyX]

Siguiendo tu notación, efectivamente Dijkstra tiene complejidad cuadrática sobre los nodos en su implementación directa. Si lo implementas con colas de prioridad con coste logarítmico, bajas la complejidad a O((n + a)logn), que es la complejidad de BFS con un factor logarítmico extra (programándolo bien, obviamente).

Si el grafo es completo, i.e. a = n², uno quedará O(n²logn) y otro O(n²), que evidentemente es mejor.

Esto hablando de las versiones estándar de cada uno. Si se quiere rizar el rizo y hablar de la versión de Dijkstra con Fibonacci Heaps, que rara vez se usa a la práctica, entonces se acaba teniendo una complejidad teórica (no hablemos ya de las constantes debidas a implementación) de O(a + nlogn), que sigue siendo peor que un BFS.