Algoritmo dijkstra

Solo disponible en BuenasTareas
  • Páginas : 9 (2169 palabras )
  • Descarga(s) : 0
  • Publicado : 2 de marzo de 2011
Leer documento completo
Vista previa del texto
Algoritmo Dijkstra
Introducción
Algoritmos de ruteo
Cuando un paquete llega a un router, éste determina el enlace al cual el paquete debe de ser transferido y se indexa una tabla en la cual se guardan los valores de envío. Los algoritmos de ruteo, cuando operan en routers en redes de comunicaciones, tienen la peculiaridad de intercambiar y de procesar información entre routers de las tablasque utilizan para el envío de paquetes.
El trabajo de ruteo es definir caminos desde el inicio hasta el final a través de una red de routers.
El propósito de un algoritmo de ruteo es simple: dado un grupo de routers con enlaces conectando a los mismos, un algoritmo de ruteo es aquel que busca un “buen” camino desde el router fuente hasta el router destino. Usualmente, un buen camino es aquel quepresenta el menor coste de enlace.
Un grafo es usado para formular problemas de ruteo. En el contexto de ruteo en redes de comunicaciones, los nodos en una gráfica representan a los routers (que son los puntos donde se toma la decisión de la ruta del envío del paquete) y los ejes que conectan a estos nodos representan a los enlaces físicos que conectan a dichos routers.
En la siguiente figurase muestra una representación abstracta de una topología de seis nodos. Como podemos observar en el modelo, para cada eje o enlace se tiene un valor, dicho valor representa el costo o peso del enlace. Usualmente el peso del enlace es reflejo de la longitud física del enlace.

El peso del enlace también es reflejo de varios factores como la velocidad del enlace, el costo monetario asociado alenlace, etc. Para cualquier eje (x, y) dentro de E vamos a de denotar c(x, y) para el costo del enlace entre los nodos x y y Si el par (x, y) no existe en E entonces definimos (x, y) =∞ .
Un nodo y se dice que es vecino de un nodo x si (x, y) pertenece a E . Dados los costes de los ejes (o enlaces), el principal objetivo de un algoritmo de ruteo es identificar el camino con menor coste entre un nodoinicial (o fuente) y un nodo final (o destino).
Para profundizar un poco en el tema definamos que el camino en un grafo G = (N, E) es una secuencia de nodos (x1,x2,…,xp ) tales que cada par de nodos (x1, x2, ), (x1, x3), (xp-1, xp) pertenezcan a los ejes E. El coste del camino (x1, x2, …, xp)es simplemente la suma de todos los costes de los ejes a lo largo del camino, esto es cx1, x2+ cx1,x3+ c(xp-1, xp). Dados cualquier par de nodos "x" y "y" , usualmente hay muchos caminos entre estos nodos, y cada camino con su respectivo coste asociado. Uno o más de estos caminos es el camino de menor coste. Así, el problema del camino del menor coste es claro: Encontrar un camino entre una fuente y un destino que tenga el menor coste.

Algoritmo de Dijkstra
El algoritmo de Dijkstra, tambiénllamado 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 yque 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 nodosque en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Análisis del algoritmo Dijkstra

En un algoritmo de estado enlace, la topología de la red y todos los costes de enlaces son conocidos. Esto se puede obtener haciendo que cada nodo realice una transmisión de paquetes estado enlace hacia todos los demás nodos en la red. Cada paquete...
tracking img