Algoritmo de Kruskal

Kruskal

El algoritmo de Kruskal es un algoritmo (ávido) de la teoría de grafos para encontrar un árbol de recubriumiento mínimo en un grafo conexo y ponderado.
Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo

En este caso me limitaré al caso de grafos conexos con costos no negativos en sus aristas

Funcionamiento:

Se parte colocando todos los vértices del grafo separados, y se decide partir por un vértice de "Inicio".

Dado el vértice actual (en el comienzo es el de inicio), armamos una lista de todas las aristas que posee, ordenadas en forma decreciente según su ponderación (costo de la arista).

Tomamos la de menor coste, retiramos de la lista de candidatos a la arista utilizada y agregamos las nuevas aristas que nos proporciona el nuevo vértice.

Así sucesivamente, generando subgrafos conexos hasta llegar a conectar todos los subgrafos conexos formando un Árbol de cubrimiento de costo mínimo.

Un excelente ejemplo se encuentra en el artículo dedicado a este algoritmo en wikipedia

Algoritmo de Dijkstra

Dijkstra en un algoritmo voraz que sirve para hallar la menor distancia entre dos nodos en un grafo conexo, acíclico, dirijido y con costos no negativos en sus aristas.

De esto hay mucho en wikipedia, por lo que solo me voy a limitar a dar algunas consideraciones que, en el estudio de este algoritmo fueron apareciendo a mi vista :D

El algoritmo sirve para hallar el mínimo camino entre un par de nodos o bien si es aplicado a cada par de nodos, obtendremos el mínimo camino entre todo par de nodos.

El algoritmo no necesita ser recursivo, basta usar 3 for anidados (para el caso anterior).

El orden del algoritmo para encontrar el mínimo camino entre un par de nodos es O(n^2) y para encontrar el mínimo entre todo par de nodos (usando Programación dinámica) es el mismo, notar que no depende del tipo de implementación que se use (cola de prioridad ó vector de visitados)


Inicialmente S contiene únicamente el nodo origen y al final contendráá todos los nodos de G.
En cada paso se selecciona aquél nodo de C cuya distancia al origen sea mínima y lo añadimos a S.
Cuando se detiene el algoritmo todos los nodos del grafo pertenecen a S

Pseudo-código

void dijkstra(int fuente, Grafo g, matriz costoAristas){
S = {fuente}
n = cantidadVertices(g)
for(i=0; i //vector de costos
costos[i] = costoAristas[fuente, i] //inicializo el costo desde la fuente hasta los otros vértices ( infinito en el caso que no exista relación)
//vector de camino final (si acaso necesitamos recontruir el camino más corto)
caminoRecorrido[i] = fuente
visitados[i] = 0; //inicializo un vector de nodos visitados
}
visitados[fuente] = 1;//marco a la fuente como visitada

for(i=0; i if(i != fuente){
w = obtenerMinimoVerticeDisponible(g) //esto es : el minimo del conjunto (V - S)
S = S U {w} //agrego el vértice utilizado
visitados[w] = 1 //lo marco como visitado
for(j=0; j if(visitados[j] != 1){
//que es menos costoso, ir directamente -> costos [j] o ir mediante un w intermedio?
if(costos[w] + costoAristas[w, j] < costos[j]){
//es menos costoso ir mediante w
costos[j] = costos[w] + costoAristas[w, j];
caminoRecorrido[j] = w //agrego el nodo utilizado
}
}
}
}
}
}