Grafos

Informe Algoritmos De Búsqueda De Caminos Mínimos

.

ALGORITMOS DE BUSQUEDA DE CAMINOS MINIMOS
GRAFOS
UNIVERSIDAD PEDAGÓGICA Y TECNOLÓGICA DE COLOMBIA
INGENIERÍA DE SISTEMAS Y COMPUTACIÓN
PROGRAMACION III
JEFFERSON RICARDO VIVAS TORRES
GUSTAVO ANDRES SANDOVAL FONSECA
JONATHAN PATIÑO ARISTIZABAL
JUAN SEBASTIAN DIAZ PEÑUELA

RESUMEN:
facilitarnos las búsquedas de los
elementos contenidos en ungrafo no
importando en que posición se encuentre.

En esta presentación se prentende dar a
conocer los Algoritmos De Búsqueda De
Caminos Mínimos y su funcionamiento
mediante la utilización de grafos
específicamente la temática tratada por
nuestro grupo fueron las siguientes
Dijkstra, Bellaman – Ford, Boruvka,
Busqueda A*, Cuthill-McKee, Algoritmo
de Floyd-Warshall y Johnson donde se
investigó comofuncionan y se mostraran
algunos ejemplos.

TEMATICA:
 Algoritmo de Dijkstra
El algoritmo de Dijkstra, también
llamado algoritmo
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 cada arista. Su nombre se
refiere a Edsger Dijkstra, quien lo
describió por primera vez en 1959.

INTRODUCCIÓN
En estereporte de informe analizara el
funcionamiento
de
los
algoritmos
utilizados en grafos para realizar
búsquedas por caminos mínimos el
funcionamiento de cada uno de ellos, para
esto se pretende lograr con la
presentación realizada y este informe
donde
se
explica
la
temática
anteriormente mencionada, para entender
los temas a abordar es como prerrequisito
saber o estar enterado en qué consisten
los grafosen java como es el manejo de
estos para que nos sirven y su adecuado
uso.
La búsqueda por caminos mínimos lo que
pretenden es facilitarnos el manejo de la
información y como su nombre lo indica

La idea subyacente en este
algoritmo consiste en ir explorando
todos los caminos más cortos que
parten del vértice origen y que
llevan a todos los demás vértices;
cuando se obtiene el camino más
cortodesde el vértice origen, al
resto de vértices que componen el
grafo, el algoritmo se detiene. El
algoritmo es una especialización de
la búsqueda de costo uniforme, y
como tal, no funciona en grafos con
aristas de coste negativo (al elegir
siempre el nodo con distancia
1

Informe Algoritmos De Búsqueda De Caminos Mínimos

.

menor, pueden quedar excluidos de
la búsqueda nodos que en
próximasiteraciones bajarían el
costo general del camino al pasar
por una arista con costo negativo).

 Algoritmo De Boruvka.
El algoritmo de Boruvka es un
algoritmo para encontrar el mínimo
árbol de expansión en un grafo
ponderado en el que todos sus
arcos tienen distinto peso.
Fue publicado por primera vez en
1926 por Otakar Boruvka como un
método eficiente para construir la
red eléctrica de Moravia.
Elalgoritmo comienza examinando
cada vértice y añadiendo el arco de
menor peso desde ese vértice a
otro en el grafo, sin tener en cuenta
los arcos ya agregados y continuos
uniendo estos grupos de la misma
manera hasta que se completa un
árbol que cubra todos los vértices.

 Algoritmo De Bellaman – Ford.
Este algoritmo genera el camino
mas corto en un grafo dirigido
ponderado (en el que el peso de
algunade las aristas puede ser
negativo), es lo mismo que el
Varjtral solo que en este si pueden
existir aristas negativas.
El Algoritmo de Bellman-Ford es,
en su estructura básica, muy
parecido al algoritmo de Dijkstra,
pero en vez de seleccionar
vorazmente el nodo de peso
mínimo aun sin procesar para
relajarlo, simplemente relaja todas
las aristas, y lo hace |V|-1 veces,
siendo |V| el número devértices en
el grafo. Las repeticiones permiten
a las distancias mínimas recorrer el
árbol, ya que en la ausencia de
ciclos negativos, el camino más
corto solo visita cada vértice una
vez. A diferencia de la solución
voraz, la cual depende de la
suposición de que los pesos sean
positivos,
esta
solución
se
aproxima más al caso general.

El algoritmo comienza examinando
cada vértice y añadiendo el arco...