• Unidades

  • Acerca de…


    Nombre: Adrian Ordoñez
    Ocupacion: Estudiante
    Carrera: ISC
    Intereses: Programacion

Problema de la Ruta mas Corta del Analisis de Redes

El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El 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”.

Se trata de encontrar la ruta de menor distancia, o costo ,a entre el punto de partida o nodo inicial y el destino o nodo terminal.

Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas de redes de comunicaciones.

Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.

Este algoritmo calcula el camino mínimo de un nodo a a otro nodo z en particular, a la vez que calcula  los caminos mínimos desde el nodo inicial a dado hasta cada uno de los otros nodos del grafo.

Consiste en encontrar la ruta más corta entre dos nodos dados de un grafo dirigido y valuado (con capacidades).

Veremos dos algoritmos, por un lado el algoritmo de Dijkstra, que encuentra el camino más corto entre el nodo origen y cada uno de los otros nodos de la red, y por otro lado el algoritmo de Floyd, que encuentra el camino más corto entre cualquier par de nodos de la red.

Algoritmo de Floyd

El algoritmo de Floyd es más general que el de Dijkstra, ya que determina la ruta más corta entre dos nodos cualquiera de la red.

  • El algoritmo representa una red de n nodos como una matriz cuadrada de orden n, la llamaremos matriz C. De esta forma, el valor Cij representa el coste de ir desde el nodo i al nodo j, inicialmente en caso de no existir un arco entre ambos, el valor Cij será infinito.
  • Definiremos otra matriz D, también cuadrada de orden n, cuyos elementos van a ser los nodos predecesores en el camino hacia el nodo origen, es decir, el valor Dij representará el nodo predecesor a j en el camino mínimo desde i hasta j. Inicialmente se comienza con caminos de longitud 1, por lo que Dij = i.
  • Las diagonales de ambas matrices representan el coste y el nodo predecesor para ir de un nodo a si mismo, por lo que no sirven para nada, estarán bloqueadas.

Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes: 

  • Formar las matrices iniciales C y D.
  • Se toma k=1.
  • Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i≠k, j≠k e i≠j, hacemos:

Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj

En caso contrario, dejamos las matrices como están. 

  • Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las iteraciones.
  • La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino óptimo para ir de un vértice a otro.

Explicacion Parte 1 

Explicacion Parte 2

 

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 dirigido y 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 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 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 costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Tendremos a lo largo de todo el proceso dos conjuntos y dos vectores:

  • Conjunto C : Conjunto de vértices candidatos. Inicialmente contiene todos los nodos menos el nodo origen.
  • Conjunto S : Conjunto de vértices seleccionados, es decir, aquellos para los que ya conocemos su camino mínimo desde el nodo origen. Inicialmente contiene el nodo origen.
  • Vector D : Almacenará la longitud del camino más corto desde el origen a cada nodo. Tendrá tantas posiciones como nodos tenga el grafo. El coste de ir del nodo origen a sí mismo lo estimaremos como cero.
  • Vector P : Almacenará el nodo predecesor a cada nodo en el camino más corto desde el origen hasta él. Tendrá tantas posiciones como nodos tenga el grafo. La posición del nodo predecesor al origen estableceremos que sea cero para indicar que es el nodo origen.
  • Llamaremos al nodo origen o, y el coste de ir del nodo i al nodo j lo denotaremos como COSTEij .

Hay que seguir los siguientes pasos: 

  • Seleccionamos el nodo que sea destino de la arista con menor valor que salga del nodo o, llamémoslo u. Introducimos el nodo u en S y lo sacamos de C. Almacenamos en la posición u del vector D el valor COSTEou y en la posición u del vector P el valor del nodo predecesor, es decir, o.
  • Seleccionamos el siguiente nodo al que podamos llegar con menor coste, bien directamente desde o, bien a través del otro nodo seleccionado u. Llamamos al nuevo nodo seleccionado v. Introducimos el nodo v en S y lo sacamos de C. Introducimos en la posición v del vector D el coste de llegar al nodo v, si es directamente desde o será COSTEov, si es a través de u será D[u]+COSTEuv. Por último, en la posición v del vector P introducimos el valor del nodo predecesor, ya sea o o u.
  • Repetiremos este proceso hasta que todos los nodos hayan sido seleccionados, es decir, hasta que el conjunto C esté vacío, o lo que es lo mismo, hasta que en el conjunto S se encuentren todos los nodos del grafo. En ese momento en el vector D tendremos almacenado el coste mínimo para llegar desde el nodo origen a cualquier nodo del grafo, y podremos obtener el camino más corto mediante el vector P.

 

Explicacion

About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: