Luis Manuel Monroy García
Matemáticas discretas
Ingeniería de Sistemas
Universidad Simón Bolívar
Algoritmo de
dijkstra
Algoritmo de la ruta más corta:
Es un algoritmo de búsqueda grafica que
resuelve solo la fuente más corta de un
problema del camino para un gráfico con los
negativos de bordes costos de ruta,
produciendo un camino más corto al árbol.
Este algoritmo se utiliza a menudo en la ruta
y como una subrutina en otros algoritmos de
grafos.
Para una fuente dada de vértice (nodo) en el
gráfico, el algoritmo encuentra la ruta con
menor coste (es decir, el camino más corto)
entre el vértice y cualquier otro vértice.
Ejemplo
Si los vértices de una gráfica representan las
ciudades y los costos de borde de ruta
representan conducir distancias entre pares
de ciudades conectadas por un camino
directo, el algoritmo de dijkstra se puede
utilizar para encontrar la ruta más corta
entre una ciudad y todas las demás ciudades.
Como resultado, el camino más corto primera
vez ampliamente utilizado en la red los
protocolos de enrutamiento, en especial IS-IS
y OSPF (Open ShortestPathFirst).
Modelo de la ruta más corta:
El problema de la ruta más corta incluye un
juego de nodos conectados donde solo un
nodo es considerado como el origen y solo
un nodo es considerado como el nodo
destino. Su objetivo es determinar un
camino de conexiones que minimizan la
distancia total del origen al destino. El
problema se resuelve por el “algoritmo de
etiquetado”. La esencia del procedimiento
es que analiza toda la red a partir del
origen; identifica de manera sucesiva la ruta
más corta a cada uno de los nodos en orden
ascendente de sus distancias (más cortas),
desde el origen; el problema queda resuelto
en el momento de llegar al nodo destino.
Definición del problema:
Setiene n nodos, partiendo del nodo inicial1 y
terminando en el nodo final n.
Arcosbi-direccionales conectan los nodos con
distancias mayores que cero.
Sedesea encontrar la ruta de mínima distancia que
conecta el nodo 1 con el nodo n.
Pormedio de la aplicación del algoritmo de este
problema podemos conocer la menor distancia
entre un nodo origen y un nodo destino.
Pasos a seguir:
Elaborarun cuadro con todos los nodos y los ramales
que salen de él.
Partiendo del origen, debemos encontrar el nodo más
cercano a él.
Anulartodos los ramales que entren al nodo más cercano
elegido.
Comenzando en el origen se debe encontrar el nodo más
cercano a él, por intermedio del nodo ya elegido y volver
al tercer paso hasta llegar al destino.
Algoritmo de Dijkstra: CAMINO MAS
CORTO
Este algoritmo también llamado algoritmo de caminos
mínimos, es un algoritmo para la determinar 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.
Allí se determina la ruta más corta desde un nodo
origen hacia los demás nodos.
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 corto
desde el vértice origen, al resto del vértices que
componen el grafo, el algoritmo se detiene.
El algoritmo es una especialización de la búsqueda
de costos uniforme, y como tal, no funciona en
grafos con aristas de costo negativo(al elegir
siempre el nodo con distancia menor, pueden
quedar excluidos de la búsqueda de nodos que en
próximas iteraciones bajarían el costo general del
camino al pasar por una arista con costo negativo).
Ruta más corta – solución por el algoritmo de
Dijkstra:
Para solucionar el problema de la ruta más corta entre dos
nodos de un grafo se puede utilizar el algoritmo de Dijkstra, el
cual sigue el siguiente procedimiento para calcular la ruta más
corta desde el nodo origen hasta cada uno de los nodos del
grafo:
Crearuna lista de nodos para almacenar los nodos con
distancia mínima ya calculada
Crearuna cola de prioridad para los nodos pendientes de
evaluar
Inserta el nodo de origen a la cola de prioridad
Mientras que haya nodos en la cola de prioridad
Ejemplo
Si los pesos de mis aristas son de valor 1,
entonces bastará con usar el
algoritmo de BFS.
Si los pesos de mis aristas son negativos no
puedo usar el algoritmo de dijsktra, para
pesos negativos tenemos otro algoritmo
llamado Algoritmo de Bellmand-Ford.
Algoritmo de
Bellman-Ford
El algoritmo de Bellman-Ford
Este algoritmo es una 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
pasos sean positivos, esta solución se aproxima más al caso
general.
Versiones del algoritmo
de Bellman-Ford
Versión no optimatizada para
grafos con ciclos negativos, cuyo
coste de tiempo es O(VE)
Versión optimatizada para grafos
con aristas de peso negativo, pero
en el grafo no existen ciclos de
coste negativo, cuyo coste de
tiempo, es también O (VE).
Versiones del algoritmo
de Bellman-Ford
Una variante distribuida al algoritmo del
Bellman-Ford se usa en protocolos de
encaminamiento basados en vector de distancias,
por ejemplo el protocolo de encaminamiento de
información (RIP). El algoritmo es distribuido
porque envuelve unas series de nodos (routers)
dentro de un sistema autónomo (AS), un conjunto
de redes y dispositivos router IP administrados
típicamente por un Proveedor de Servicios de
Internet (ISP).
Se compone de los siguientes pasos:
Cadanodo calcula la distancia entre
el mismo y todos los demás dentro
de un AS y almacena esta
información en una tabla.
Cadanodo envía su tabla a todos los
nodos vecinos.
Cuando un nodo recibe las tablas de
distancias de sus vecinos, este
calcula la ruta más corta a los
demás nodos y actualiza su tabla
para reflejar los cambios.
Las desventajas principales del algoritmo
de Bellman-Ford en este ajuste son:
No es escala bien.
Los cambios en la topología de red no se reflejan
rápidamente ya que las actualizaciones se
distribuyen nodo por nodo.
Contando hasta el infinito (si un fallo de enlace o
nodo hace que un nodo sea inalcanzable desde un
conjunto de otros nodos, estos pueden estar
siempre aumentando gradualmente sus cálculos de
distancia a él, y mientras tanto puede haber
bucles de enrutamiento).
Algoritmo de
Floyd-Warshall
Algoritmo de Floyd-Warshall
El problema que intenta resolver
este algoritmo es el de encontrar el
camino más corto entre todos los pares
de nodos o vértices de un grafo. Esto es
semejante a construir una tabla con
todas las distancias mínimas entre pares
de ciudades de un mapa, indicando
además la ruta a seguir para ir de la
primera ciudad a la segunda. Este es
uno de los problemas más interesantes
que se pueden resolver con algoritmos
de grafos.
Existen varias soluciones a este problema y
los algoritmos a aplicar dependen también de
la existencia de arcos con pesos o costes
negativos en el grafo. En el caso de no existir
pesos negativos, sería posible
ejecutar V veces el algoritmo de Dijkstra
para el cálculo del camino mínimo, donde V
es el número de vértices o nodos del grafo.
Esto conllevaría un tiempo de ejecución de O
(V^3) (aunque se puede reducir).
Si existen arcos con pesos negativos, se
puede ejecutar también V veces el Algoritmo
de Bellman-Ford, una vez para cada nodo del
grafo. Para grafos densos (con muchas
conexiones o arcos) esto conllevaría un
tiempo de ejecución de O (V^4).
El algoritmo de Floyd-Warshall (‘All-Pairs-
Shortest-Path’ – Todos los caminos mínimos)
ideado por Floyd en 1962 basándose en un
teorema de Warshall también de 1962, usa la
metodología de Programación Dinámica para
resolver el problema. Éste puede resolver el
problema con pesos negativos y tiempos de
ejecución iguales a O (V^33); sin embargo,
para ciclos de peso negativo el algoritmo
tiene problemas. A continuación se muestra
el pseudocódigo del algoritmo:
