Un grafo está formado por nodos y aristas. Cada arista de nuestro ejemplo tiene un peso positivo, es decir, un coste: puede representar distancia, tiempo o energía. Usamos grafos no dirigidos y conexos: todos los nodos son alcanzables entre sí.
La misma red plantea preguntas diferentes. Dijkstra encuentra caminos de coste mínimo desde un nodo inicial. Prim y Kruskal buscan, en cambio, un árbol que conecte todos los nodos sin ciclos y con la menor suma de pesos. Un camino mínimo y un árbol de expansión mínima no son el mismo objeto.
Un pequeño ejemplo común
Considera cuatro nodos A, B, C, D y las aristas A–B de peso 4, A–C de peso 2, B–C de peso 1, B–D de peso 5 y C–D de peso 8. De A a D, el camino A–C–B–D cuesta 2+1+5=8; A–B–D cuesta 9 y A–C–D cuesta 10. Un árbol mínimo elige B–C, A–C y B–D, con peso total 1+2+5=8. La coincidencia del número 8 es casual: el primer problema mide una ruta y el segundo una red que conecta a todos.
1. Dijkstra: fijar distancias cada vez más seguras
Se asigna distancia 0 al origen y distancia provisional infinita a los demás nodos. En cada paso se elige el nodo no fijado con la menor distancia provisional. Después se intenta mejorar la distancia de sus vecinos sumando el peso de cada arista. Con pesos no negativos, la distancia elegida es definitiva. En el ejemplo, desde A descubrimos C con coste 2 y B con coste 4; pasando por C mejoramos B a 3; por B llegamos a D con coste 8.
Límite importante: este razonamiento no funciona en general con pesos negativos.
2. Prim: hacer crecer un árbol
Se elige un nodo inicial. En cada paso se toma la arista de menor peso que conecta un nodo del árbol con otro que está fuera. El grupo conectado crece sin formar ciclos hasta incluir todos los nodos. Prim observa siempre la frontera del árbol actual: su elección depende de la red ya construida.
3. Kruskal: ordenar las aristas y evitar ciclos
Se ordenan todas las aristas de menor a mayor peso. Se acepta una si une dos grupos antes separados; se descarta si cerraría un ciclo. Los grupos se fusionan hasta formar un único árbol. Prim y Kruskal pueden elegir aristas distintas cuando hay empates, pero el peso total mínimo coincide.
Prueba el mismo grafo
En el laboratorio interactivo de grafos ponderados puedes generar un grafo aleatorio conexo de 20 a 100 nodos con pesos enteros entre 1 y 20. La semilla reproduce el mismo grafo; elige origen y destino para Dijkstra y luego compara Prim y Kruskal en la misma red. Avanza paso a paso o inicia la animación. La posición de los nodos facilita la lectura, pero la longitud visual de una arista no es su peso.
Qué comparar
En Dijkstra observa cómo mejora una distancia provisional antes de ser definitiva. En Prim y Kruskal compara el peso total final: debe coincidir aunque cambie el orden de las elecciones. En un grafo grande puedes ocultar los números de los pesos para ver mejor la estructura; el peso de la arista examinada sigue visible.