Algoritmo de Dijkstra: ejemplo resuelto y caminos mínimos

El algoritmo de Dijkstra encuentra caminos de costo mínimo desde un origen en un grafo con pesos no negativos. Mantiene una distancia provisional para cada vértice, selecciona el pendiente con menor costo acumulado y revisa si pasar por él mejora las rutas conocidas. El costo de un camino es la suma de los pesos de sus aristas.

La decisión utiliza la distancia total desde el origen, no simplemente la arista más pequeña del dibujo. Un ejemplo dirigido con cinco vértices permitirá seguir cada actualización, reconstruir la ruta final y entender por qué los pesos negativos impiden la garantía de la versión clásica.

Definir el grafo antes de empezar

Un grafo contiene vértices y aristas. En uno dirigido, cada arco tiene una orientación que debe respetarse. Si existe S → A, no se puede suponer que también existe A → S. Los pesos pueden representar minutos, kilómetros o costos abstractos, pero deben ser comparables y sumables según el objetivo del modelo.

La documentación de NetworkX sobre caminos mínimos distingue el número de aristas del costo ponderado. Con pesos diferentes, un recorrido de tres aristas puede resultar más barato que otro de una sola. Dijkstra resuelve la segunda pregunta cuando se cumple la condición de no negatividad.

En nuestro grafo hipotético, los vértices son S, A, B, C y T. Los arcos y pesos son: S → A: 7; S → B: 2; B → A: 3; B → C: 6; A → C: 1; A → T: 9; C → T: 2; B → T: 12. No existen otros arcos ni direcciones inversas implícitas.

Distancias provisionales y relajación

Al comenzar, d(S) = 0 y las demás distancias valen infinito, porque todavía no se conoce un camino desde S. Infinito es una marca conceptual de ausencia de ruta descubierta; no es un peso de una arista real. También se guarda un predecesor por vértice para reconstruir posteriormente un camino.

La relajación de u → v compara d(v) con d(u) + w(u,v). Si el segundo valor es menor, se actualiza d(v) y se registra u como predecesor de v. Si no mejora, se conserva la información anterior. El proceso requiere que d(u) represente un camino conocido; no se inventan costos desde vértices aún inalcanzables.

Se llama finalizado a un vértice cuya distancia mínima ya quedó establecida por la selección correcta. La distinción entre descubierto y finalizado es esencial. Una implementación que marca un vértice como cerrado al insertarlo por primera vez puede impedir mejoras necesarias y producir una respuesta errónea.

Ejemplo resuelto: de S a T

Después de S se selecciona B, porque su distancia provisional es 2. Sus arcos proponen A con costo 5, C con costo 8 y T con costo 14. Después se selecciona A, cuyo costo 5 es el menor pendiente. Desde A se mejora C a 6; la propuesta para T cuesta 14 y no reduce su valor.

El siguiente seleccionado es C, con distancia 6. El arco C → T propone 6 + 2 = 8, mejor que 14. Finalmente se selecciona T con distancia 8. Si solo interesa ese destino, este es el momento adecuado para detenerse: la distancia de T ya fue finalizada.

Los predecesores finales son B para A, S para B, A para C y C para T. Para recuperar la ruta, se empieza en T y se retrocede: T, C, A, B, S. Al invertir esa secuencia se obtiene S → B → A → C → T. Su costo es 2 + 3 + 1 + 2 = 8.

El camino usa cuatro arcos, mientras que S → A → T usa dos y cuesta 16. El recorrido S → B → T cuesta 14. Comparar estas alternativas ayuda a comprobar que el objetivo no es reducir pasos. La prueba general del algoritmo, sin embargo, no consiste en enumerar solo algunas rutas favorables.

Por qué funcionan los pesos no negativos

Suponga que u es el vértice pendiente con menor distancia provisional. Cualquier ruta alternativa que llegue a u a través de otro pendiente necesitaría pasar primero de la zona finalizada a la pendiente. Con pesos no negativos, continuar ese recorrido no puede reducir el costo acumulado para producir una mejora oculta menor que la selección actual.

Esa propiedad sostiene la decisión de finalizar u. El material de análisis de algoritmos de la USP desarrolla el problema de distancias ponderadas y la condición de no negatividad. Los pesos cero son compatibles con la condición; lo que la rompe en general son los negativos.

Considere otro grafo dirigido: S → A cuesta 2; S → B cuesta 5; B → A cuesta −4. La versión clásica finaliza A con 2 antes de procesar B, pero S → B → A cuesta 1. Si A ya se cerró, su distancia queda incorrecta. No hace falta un ciclo negativo para que falle esa lógica.

Procedimiento y cola de prioridad

Una búsqueda lineal del siguiente mínimo puede producir una implementación de costo O(V² + E), con V vértices y E aristas. Con listas de adyacencia y una cola binaria de prioridad con actualización de claves, una cota habitual es O((V + E) log V). El costo depende de las estructuras y operaciones implementadas.

La documentación de heapq en Python explica la propiedad que mantiene el mínimo accesible en la raíz. Si se usa una estrategia de insertar entradas nuevas en vez de actualizar las antiguas, habrá registros obsoletos que deben descartarse al extraerlos. La cola no reemplaza esa comprobación lógica.

Al reproducir el ejemplo con software de programación, verifique las claves donde se guardan pesos y las convenciones de la biblioteca. NetworkX, por ejemplo, puede asumir peso 1 si falta el atributo solicitado. Un dato omitido podría cambiar silenciosamente el problema en vez de producir un error visible.

BFS, Bellman–Ford y árbol de expansión

La búsqueda en anchura, o BFS, encuentra caminos con el menor número de aristas en un grafo sin ponderación. Si todos los pesos son iguales y positivos, también minimiza su suma. Para pesos diferentes no negativos, Dijkstra ofrece la herramienta apropiada; para negativos, Bellman–Ford permite otro análisis, incluida la detección de ciclos negativos alcanzables.

Un árbol de expansión mínima responde a otra pregunta: conectar todos los vértices de un grafo no dirigido minimizando el peso total del árbol. No garantiza caminos mínimos desde un origen. Que Dijkstra pueda producir un árbol de predecesores no convierte ambos problemas en equivalentes.

Un diagrama de flujo puede mostrar selección, relajación y repetición. Para comprobar una implementación se necesita además registrar estados: distancias, pendientes y predecesores. En el ejemplo, una prueba significativa debe esperar costo 8 y una ruta válida, además de verificar la suma de sus arcos.

¿Qué sucede si dos rutas tienen el mismo costo?

Puede haber varios caminos mínimos. El orden de procesamiento y la política ante empates determinan cuál se devuelve si solo se guarda un predecesor. La distancia mínima sigue siendo la misma. Un test no debe exigir una ruta única cuando las reglas permiten alternativas equivalentes.

¿Y si el destino no es alcanzable?

Su distancia permanece infinita en la descripción conceptual. Una biblioteca puede devolver un estado particular o generar una excepción, según su interfaz. La función single_source_dijkstra de NetworkX documenta sus resultados y límites. Ningún camino debe reconstruirse a partir de predecesores inexistentes.