EJEMPLOS DE
ALGORITMOS CODICIOSOS
Presentado por:
Marcelo Gabriel Ramos Torres
Bryan Steve Montañez Quilla
Edgar Enrique Vargas Huaman
ALGORITMO DE PRIM
Este algoritmo fue desarrollado por primera vez por el matemático checo
Vojtêch Jarník, no sería hasta más tarde, en 1957, cuando aparecería publicado de
forma independiente bajo la autoría del ingeniero informático estadounidense
Robert C. Prim. Es él quien le dio fama y por cuyo apellido es hoy conocido.
Es el primero y el más sencillo de los algoritmos de la teoría de grafos para
encontrar un árbol generador mínimo en un grafo ponderado, en otras palabras,
el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos
los vértices, donde el peso total de todas las aristas en el árbol es el mínimo
posible.
EJEMPLO
ALGORITMO DE KRUSKAL
Fue escrito y desarrollado por Joseph Kruskal, publicado por primera vez en el
año 1956. Es un algoritmo codicioso que sirve para encontrar el árbol de
expansión mínima en un grafo conexo y ponderados. Se busca la arista de menor
peso o valor, y se une los vértices siempre y cuando no se forme un ciclo .Esto se
hace hasta que todos los vértices estén comprendidos en el árbol. Para
comprobar que el árbol de expansión mínima este hecho se revisa que el número
de aristas sea igual al numero de vértices menos 1.
EJEMPLO
ALGORITMO DE DIJKSTRA
HISTORIA
Fue creado y publicado por el Dr. Edsger W. Dijkstra, un científico Neerlandés en ciencias de la computación e
ingeniería de software.
En 1959, publicó un artículo de tres páginas titulado: "A note on two problems in connexion with graphs".En
ese artículo explicó su nuevo algoritmo.
ALGORITMO
DIJKSTRA
El algoritmo de Dijkstra te permite
calcular la ruta más corta entre un
nodo (tú eliges cuál) y todos los demás
nodos en el gráfo ponderado con
valores no negativos.
PROCEDIMIENTO
Comienza desde el nodo inicial y explora
de manera iterativa los nodos vecinos,
seleccionando siempre el nodo más
cercano al nodo inicial en cada paso. Este
proceso continúa hasta que se hayan
visitado todos los nodos o se haya
alcanzado el nodo de destino, calculando
así la distancia más corta desde el nodo
inicial a cada nodo en el grafo.
APLICACIONES
01 02 03 04
ENRUTAMIENTO SISTEMAS DE PLANIFICACIÓ DISEÑO DE
DE REDES NAVEGACIÓN N DE CIRCUITOS
Y MAPAS PROYECTOS INTEGRADOS
Se utiliza en protocolos En aplicaciones de GPS En la gestión de Se aplica en el diseño
de enrutamiento de y mapas en línea, el proyectos, puede de circuitos integrados
distancia para algoritmo de Dijkstra se utilizarse para para encontrar las rutas
encontrar las rutas más utiliza para encontrar la determinar la ruta más cortas entre
cortas en redes de ruta más corta entre crítica y minimizar el componentes en un
computadoras. dos ubicaciones. tiempo necesario para chip.
completar un proyecto.
EJEMPLO
Durante la ejecución del algoritmo, iremos marcando cada nodo con su distancia
mínima al nodo inicial (nuestro nodo elegido). Para ello esta distancia es 0. Para el
resto de nodos, como todavía no conocemos esa distancia mínima, empieza a ser
infinita (∞):
EJEMPLO
Ahora, revisaremos los vecinos de nuestro nodo actual (A, B y D) en cualquier orden. Empecemos
con B. Sumamos la distancia mínima del nodo actual (en este caso, 0) con el peso de la arista
que conecta al nodo actual con B (en este caso, 7), y obtenemos 0 + 7 = 7. Comparamos ese valor
con la distancia mínima de B (infinito); el valor más pequeño es el que queda como la distancia
mínima de B (en este caso, 7 es menos que infinito):
EJEMPLO
Ahora revisaremos al vecino A. Sumamos 0 (la distancia mínima de C, nuestro nodo
actual) con 1 (el peso de la arista que conecta nuestro nodo actual con A) para
obtener 1. Comparamos ese 1 con la distancia mínima de A (infinito ) y dejamos el
menor valor:
EJEMPLO
Repetimos el procedimiento para D:
EJEMPLO
Hemos revisado todos los vecinos de C. Por ello, lo marcamos como visitado .
Representamos a los nodos visitados con una marca de verificación verde:
EJEMPLO
Ahora debemos seleccionar un nuevo nodo actual . Ese nodo debe ser el nodo no
visitado con la menor distancia mínima, es decir, el nodo con el menor número y sin
marca de verificación verde. En este caso, ese nodo es A. Vamos a marcarlo con el
punto rojo:
EJEMPLO
Revisamos los vecinos de nuestro nodo actual, ignorando los visitados. Esto significa que solo
revisaremos B.
Para B, sumamos 1 (la distancia mínima de A, nuestro nodo actual) con 3 (el peso de la arista
conectando a A con B) para obtener 4. Comparamos ese 4 con la distancia mínima de B (7) y
dejamos el menor valor: 4.
EJEMPLO
Después, marcamos A como visitado y elegimos un nuevo nodo: D, que es el nodo no visitado con la menor distancia
mínima.
Esta vez, revisamos B y E.
Para B, obtenemos 2 + 5 = 7. Comparamos ese valor con la distancia mínima de B (4) y dejamos el menor valor (4).
Para E, obtenemos 2 + 7 = 9, lo comparamos con la distancia mínima de E (infinito) y dejamos el valor menor (9).
EJEMPLO
Marcamos D como visitado y establecemos nuestro nodo actual en B.
EJEMPLO
Sólo debemos verificar E. 4 + 1 = 5, que es menos que la distancia mínima de E
(9), así que dejamos el 5. Marcamos B como visitado y establecemos E como el
nodo actual.
EJEMPLO
E no tiene vecinos no visitados, así que no verificamos nada. Lo marcamos como visitado.
Como no hay nodos no visitados, ¡terminamos! La distancia mínima de cada nodo ahora representa la
distancia mínima entre ese nodo y el nodo C (el nodo que elegimos como nodo inicial).
