Algoritmos de Busqueda



Instituto Tecnológico de Costa Rica
Escuela de Electrónica
Análisis de Algoritmos de Prim, Kruskal y Dijkstra
Profesor: Víctor Garro Abarca.
Estudiantes:
César Jesús Pérez Álvarez.
FelipeHerrero Chavarría.
Jorge Alberto Grimaldi Barahona.

Grupo: 3
I Semestre
2013


Algoritmo de Prim:
Ejecutando los programas HTM del algortimo PRIM, se puede ver cómo funciona dicho proceso.Se selecciona un nodo al azar, en casi todos los casos el nodo "0" ó el nodo "a". De ahí se tomará en cuenta las aristas más cercanas a dicho nodo y se selecciona la de menor valor. Además se enlazaráal nuevo árbol el nuevo nodo. Luego se añadirán a la "lista de consideración" las aristas más cercanas al nuevo nodo al que se llegó. Así sigue hasta tener todos los nodos enlazados. Se deben tenercuidado de no crear ciclos entre los nodos ya enlazados.

Algortimo de Kruskal:
El proceso a la hora de ser corrido es muy similar al del algoritmo de Prim, pero su proceso de selección varía.Primero ordena a todas las aristas de menor a mayor según su peso. Comienza a incorporar al nuevo árbol pero cuidando de que la arista seleccionada no forme un ciclo con las otras ya enlazadas. Cuandoselecciona una aristas "marca" a los nodos de dicha arista. Termina el proceso cuando todos los nodos están marcados. Importante recalcar que a diferencia del algoritmo de Prim este elige según el valorasignado a las aristas y no a los nodos.

Algortimo de Dijkstra:
El proceso de selección es más complejo en este. Parecido al del algoritmo de prim, pero ahora se van sumando los valores de lasaristas según el camino recorrido. En el ejemplo 1 de la página HTM, se ve que al seleccionar el primer nodo, todo sigue igual, luego se elige el nodo vecino cuyo camino sea de menor valor. Pero al tratarde elegir el siguiente nodo, los valores cambian, ahora u4 vale 15 en vez de 16. Esto pasa cuando existen 2 caminos posibles a ese nodo. En cuyo caso se toma el de menor valor. En el algoritmo de...