Post actualizado el día octubre 29, 2026 by DeiviSanzPlay
Si has buscado algoritmo de grafos Dijkstra probablemente vienes de un examen, de un bug raro en tu código o de una entrevista técnica donde te preguntaron por qué no sirve para cualquier grafo. La respuesta corta: Dijkstra asume que cualquier camino que alargas ya no puede volverse más corto, y eso solo se cumple si todos los pesos son no negativos. Cuando aparece una arista negativa, esa suposición se rompe y el resultado puede ser incorrecto sin lanzar ningún error.
Lo he visto en proyectos reales de rutas con descuentos: un tramo que «resta» kilómetros efectivos porque representa una autopista con peaje subvencionado. El algoritmo devolvía una ruta plausible, pero no la óptima. Nadie se dio cuenta hasta que comparamos con Bellman-Ford.
El fallo clásico: nodos ya cerrados que dejan de revisarse
Dijkstra mantiene dos conjuntos: nodos con distancia definitiva y nodos pendientes. Extrae el nodo con menor distancia tentativa, lo marca como cerrado y relaja sus vecinos. Ese cierre es la clave del problema. Si más adelante aparece una arista negativa que mejora la distancia de un nodo ya cerrado, el algoritmo no vuelve atrás.
Un ejemplo mínimo: A→B con peso 1, A→C con peso 5, C→B con peso −10. La ruta real más corta de A a B es A→C→B con coste −5, pero Dijkstra cierra B en cuanto lo alcanza desde A con distancia 1. El resultado final es 1, no −5. El código no falla, simplemente miente.
Cuándo sí es la elección correcta (y cuándo no)
El algoritmo de grafos Dijkstra brilla cuando los pesos son positivos y el grafo es grande y disperso. Con un heap binario la complejidad ronda O((V+E) log V), y con un heap de Fibonacci baja a O(E + V log V). En mapas viales, redes de fibra o rutas de reparto con distancias físicas, es imbatible en la práctica frente a Bellman-Ford, que es O(V·E).
No lo uses si:
- Hay aristas con peso negativo, aunque sea una sola.
- Necesitas detectar ciclos de peso negativo (eso es territorio de Bellman-Ford).
- El grafo es denso y pequeño: Floyd-Warshall puede ser más simple de implementar y suficientemente rápido.
- Los pesos cambian dinámicamente mientras consultas: considera A* o algoritmos incrementales.
Un matiz importante: existen variantes como Johnson que reescriben los pesos con potenciales para eliminar los negativos y luego aplican Dijkstra. Es una salida elegante si tienes un grafo con pesos mixtos y quieres reutilizar tu implementación rápida.
El error de implementación más frecuente en entrevistas
Más allá de los pesos negativos, el fallo que más veo al revisar código es actualizar la distancia de un nodo ya extraído del heap sin comprobar si su entrada está obsoleta. En lenguaje coloquial: metes el mismo nodo varias veces en la cola con distintas distancias y, al sacarlo, no verificas si la distancia actual coincide con la almacenada en el heap. El algoritmo sigue funcionando, pero procesa trabajo redundante y en grafos grandes se nota.
La solución habitual es mantener un diccionario de distancias y, al extraer un nodo, comprobar if d != distancias[nodo]: continue. Es una línea, pero marca la diferencia entre una solución aceptable y una que se queda sin tiempo en pruebas de estrés.
Alternativas y comparación honesta
Para el camino más corto con pesos negativos, Bellman-Ford es el estándar. Para grafos con heurística geográfica, A* reduce exploración drásticamente. Para todos los pares de nodos en grafos pequeños, Floyd-Warshall gana en simplicidad. Y si solo necesitas alcanzar un destino concreto en un grafo no ponderado, BFS es más rápido que cualquier variante de Dijkstra.
La documentación clásica de algoritmos (Cormen, Leiserson, Rivest y Stein en Introduction to Algorithms, y las notas de cursos universitarios de estructuras de datos) coincide en la misma advertencia: la corrección de Dijkstra depende de la no negatividad. No es un detalle menor, es la condición que sostiene toda la prueba de optimalidad.
Recomendación práctica
Antes de elegir el algoritmo de grafos Dijkstra, audita tus pesos. Si vienen de datos reales, revisa si algún proceso los puede volver negativos (descuentos, bonificaciones, logs de probabilidad). Si hay riesgo, cambia a Bellman-Ford o normaliza los pesos. Y si decides quedarte con Dijkstra, escribe un test con un grafo que tenga una arista negativa: verás cómo falla en silencio, y eso vale más que cualquier explicación teórica.
Perfiles verificables: Sitio web
Publicado el 29 de October de 2026. Última revisión: 29 de October de 2026.
