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.
Por
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:
*- se tiene n nodos, partiendo del nodo
inicial1 y terminando en el nodo final n.
*- arcos bi-direccionales conectan los
nodos con distancias mayores que cero.
*- se desea encontrar la ruta de mínima
distancia que conecta el nodo 1 con el nodo n.
Por
medio 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:
1.
Elaborar un cuadro con todos
los nodos y los ramales que salen de él.
2.
Partiendo del origen, debemos
encontrar el nodo más cercano a él.
3.
Anular todos los ramales que
entren al nodo más cercano elegido.
4.
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.
Ejemplo
del árbol de expansión mínima:
Un árbol de expansión mínima es aquel que
conecta todos los nodos dentro de una red que está en una distancia mínima y
que no contiene un ciclo.
Pasos
para elaborar un árbol de expansión mínima:
·
Seleccionar cualquier nodo de
la red o indicando según el problema
·
Colocar este nodo al más
cercano que minimice la distancia y proseguir considerando todos los nodos que
estén conectados, escogiendo de igual manera el que tenga la mínima distancia,
hasta incluir todos los nodos. Si los nodos son igual valor se selecciona uno
arbitrariamente, y esto quiere decir que puede haber más de una solución óptima.
Características:
*- determina el camino más corto dado un
vértice origen.
*- utiliza un tipo de estructura de cola
llamado cola de prioridad.
Origen
del algoritmo de dijkstra:
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.
La idea subyacente en este algoritmoconsiste
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:
·
Crear una lista de nodos para
almacenar los nodos con distancia mínima ya calculada
·
Crear una 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
ºextrae el primer
nodo de la cola de prioridad (tmp)
ºagrega el nodo tmp a
la lista de nodos ya calculados
ºgenera una lista de
los nodos conectados al nodo tmp que no estén en la lista de ya calculados
º Para cada nodo de la lista (nod)
▪ calcula la distancia al origen con la
distancia entre tmp y nod mas la distancia calculada entre el origen y tmp.
▪ Si el nodo nodestá en la cola de prioridad
lo agrega
▪ Si
el nodo nod ya está en la cola de prioridad y la distancia con la que está
guardado en la cola es menor, lo deja como esta y si no, lo actualiza con la
distancia calculada.
º Fin
·
Fin
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.
Existen dos versiones:
·
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).
Aplicaciones de encaminamiento:
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:
1.
Cada nodo calcula la distancia entre el mismo y todos los demás dentro
de un AS y almacena esta información en una tabla.
2.
Cada nodo envía su tabla a todos los nodos vecinos.
3.
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).
