Algoritmo De Kruskal Dijkstra

Kruskal y Dijkstra

Alejandra Alcántara Valencia
Josué Daniel Rodríguez Quintana

Algoritmo de Kruskal

Algoritmo de Dijkstra
Algoritmo de Dijkstra. También llamadoalgoritmo de caminos mínimos, es un
algoritmo para la determinación del camino más corto dado un vértice origen al resto
de vértices en un grafo con pesos en cadaarista. Su nombre se refiere a Edsger
Dijkstra, quien lo describió por primera vez en 1959.
Aplicaciones
En múltiples aplicaciones donde se aplican los grafos, esnecesario conocer el camino
de menor costo entre dos vértices dados:
 Distribución de productos a una red de establecimientos comerciales.

Kruskal y Dijkstra

AlejandraAlcántara Valencia
Josué Daniel Rodríguez Quintana

 Distribución de correos postales.
Sea G = (V, A) un grafo dirigido ponderado.
El problema del camino más cortode un vértice a otro consiste en determinar el
camino de menor costo, desde un vértice u a otro vértice v. El costo de un camino es
la suma de los costos (pesos) delos arcos que lo conforman.
Características del algoritmo
 Es un algoritmo greddy.
 Trabaja por etapas, y toma en cada etapa la mejor solución sin considerarconsecuencias futuras.
El óptimo encontrado en una etapa puede modificarse posteriormente si surge una
solución mejor.

Fuentes de Consulta:
Joyanes L, Zahonero I. Estructurade Datos. Algoritmos, Abstracción y Objetos. Madrid: McGraw-Hill; 199
Algoritmo de Dijkstra,http://www.ecured.cu/index.php/Algoritmo_de_Dijkstra, consultado el 25 deMayo de 2015
Algoritmo de Kruskal,http://xcodigoinformatico.blogspot.mx/2012/09/algoritmo-de-kruskal-arbol-de-expansion.html,
consultado el 25 de Mayo de 2015