5 3 Algoritmos de Recorrido y Búsqueda_5 3 1 El Camino Más Corto - Lupiwi Chan

Vista previa del material en texto

Algoritmos de 
recorrido y 
búsqueda.
EL CAMINO MÁS 
CORTO
•El algoritmo de rutas más cortas es 
en uno de los módulos de análisis 
más importantes de los algoritmos 
de grafos Este se encarga de 
detectar dentro de un grafo cuál es 
la ruta más eficiente o el recorrido 
de menor distancia entre un par 
de vértices que conforman un 
grafo. 
https://www.grapheverywhere.com/algoritmos-de-grafos/
https://www.grapheverywhere.com/algoritmos-de-grafos/
Los algoritmos más importantes para 
la solución de este problema son: 
• El algoritmo de Dijkstra: Resuelve las 
cortas de origen único problemas de ruta. 
• Algoritmo de Bellman-Ford: Resuelve el 
problema de una sola fuente, si borde 
pesos pueden ser negativos. 
• Un algoritmo de búsqueda A*: Resuelve 
para el par de ruta más corta única 
utilizando la heurística para tratar de 
acelerar la búsqueda. 
• Algoritmo de Floyd-Warshall: Resuelve 
todos los pares caminos más cortos.
• Algoritmo de Johnson: Resuelve todos los 
pares de trayectorias más cortas, y puede 
ser más rápido que Floyd-Warshall en 
grafos dispersos.
El 
algoritmo 
de 
Dijkstra.
• El conocido algoritmo Dijkstra o algoritmo de ruta 
más corta es uno de los más eficientes de esta 
familia. Nace basado en la teoría de Dijkstra que 
buscaba darle solución al legendario 
planteamiento de la teoría de grafos: conseguir 
rutas más cortas para diferentes casos. Con este 
planteamiento se logra dar una solución especial 
al dilema de los caminos cortos con un rango de 
comprensibilidad para personas que no 
pertenecen en su totalidad al mundo de la 
informática.
• Este algoritmo estudia todas y dada una de las 
conexiones que presenta un vértice dado y a 
partir de eso se determina la ruta más corta y 
eficiente para realizar el recorrido por el grafo. 
Este algoritmo se orienta principalmente a 
estudiar estructuras de grafos se ejecuta en 
tiempo real y puede ser utilizado en diferentes 
casos.
https://www.grapheverywhere.com/algoritmo-de-rutas-mas-cortas
https://www.grapheverywhere.com/algoritmo-de-rutas-mas-cortas
Algoritmo de 
Bellman-Ford.
• El algoritmo de Bellman-Ford genera el camino 
más corto en un grafo dirigido ponderado (en 
el que el peso de alguna de las aristas puede 
ser negativo). El algoritmo de Dijkstra resuelve 
este mismo problema en un tiempo menor, 
pero requiere que los pesos de las aristas no 
sean negativos, salvo que el grafo sea dirigido 
y sin ciclos. Por lo que el Algoritmo 
Bellman-Ford normalmente se utiliza cuando 
hay aristas con peso negativo. Este algoritmo 
fue desarrollado por Richard Bellman, Samuel 
End y Lester Ford.
https://es.wikipedia.org/wiki/Grafo_dirigido
https://es.wikipedia.org/wiki/Arista_(Teor%C3%ADa_de_grafos)
https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
• 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 de vé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.
Un algoritmo de 
búsqueda A*
• El algoritmo conocido como A* es 
una optimización de los postulados 
del algortimo Dijsktra para descubrir 
rutas más cortas dentro de un grafo. 
En esta modificación se toma como 
punto de inicio a la observación del 
grafo las búsquedas informadas que 
existen para tomar decisiones 
óptimas sobre los caminos a seguir. 
Su teoría tiene nacimiento en el año 
1968 y fue desarrollado 
principalmente para aportar 
elementos a la determinación de 
rutas de costo mínimo.
https://www.grapheverywhere.com/algoritmo-a
El algoritmo de 
Floyd-Warshall.
• El algoritmo de Floyd-Warshall 
es la opción utilizada cuando se 
desea determinar el camino 
mínimo entre todos los pares 
de vértices de un grafo, 
comparando todos los posibles 
caminos logra mejorar 
paulatinamente la estimación 
hasta llegar a la más óptima. 
Esto puede presentarse de 
manera más clara a través de 
un ejemplo de implementación. 
Pero antes, revisaremos el 
análisis del tiempo de ejecución 
para este caso.
El algoritmo de 
Johnson.
• El algoritmo de Johnson es una forma 
de encontrar el camino más corto entre 
todos los pares de vértices de 
un grafo dirigido disperso. Permite que 
las aristastengan pesos negativos, si 
bien no permite ciclos de peso negativo. 
Funciona utilizando el algoritmo de 
Bellman-Ford para hacer una 
transformación en el grafo inicial que 
elimina todas las aristas de peso 
negativo, permitiendo por tanto usar 
el algoritmo de Dijkstra en el grafo 
transformado. Su nombre viene de 
Donald B. Johnson, quien fuera el 
primero en publicar la técnica en 1977.
https://es.wikipedia.org/wiki/Problema_de_los_caminos_m%C3%A1s_cortos
https://es.wikipedia.org/wiki/V%C3%A9rtice_(teoria_de_grafos)
https://es.wikipedia.org/wiki/Grafo
https://es.wikipedia.org/wiki/Grafo_dirigido
https://es.wikipedia.org/wiki/Grafo_denso
https://es.wikipedia.org/wiki/Arista_(Teor%C3%ADa_de_grafos)
https://es.wikipedia.org/wiki/Ciclo_(teor%C3%ADa_de_grafos)
https://es.wikipedia.org/wiki/Algoritmo_de_Bellman-Ford
https://es.wikipedia.org/wiki/Algoritmo_de_Bellman-Ford
https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra