ALGORITMO PARA LA RUTA MAS CORTA (GRUPO 8)

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).