Dijkstra Y Floyd-Warshall

Algoritmos Dijkstra y Floyd-Warshall

1. Algoritmo de Dijkstra

La idea básica del algoritmo es la siguiente: Si P es un camino de longitud mínima s®z y P contiene al vértice v, entonces la parte s®v de P es también camino de longitud mínima de s a v. Esto sugiere que si deseamos determinar el camino óptimo de s a cada vértice z de G, podremos hacerlo en orden creciente de la distanciad(s,z).

a) Descripción del algoritmo

Entrada: Un grafo (o digrafo) G con pesos no negativos, y un vértice de partida u. El peso de una arista xy es w(xy); si xy no es una arista diremos que w(xy) = ¥.
Idea: Mantener un conjunto S de vértices a los que conocemos la distancia más corta desde u, junto con el predecesor de cada vértice de S en dicha ruta. Para lograr esto, mantenemos unadistancia tentativa t(z) desde u a cada z Î V(G). Si z Ï S, t(z) es la distancia más corta encontrada hasta ahora entre u y z. Si z Î S, t(z) es la distancia más corta entre u y z. En cualquier caso, pred[z] es el predecesor de z la ruta u® z en cuestión.

Inicialización: S = {u}, t(u)=0, t(z) = w(uz) y pred[z] = u para z ¹ u.

Iteración: Sea v Î V(G) – S, tal que:
t(z) = min{t(v) : vÎ V(G) – S }Agrégase v a S.

Para zÎ V(G) –S actualícese t(z) = min{t(z),t(v)+w(vz) }.

Si cambia t(z), cámbiese pred[z] a v.
Terminación: Termínese el algoritmo cuando S = V(G) o cuando t(z) = ¥ para todo z Î V(G) – S .
Al terminar, la distancia más corta entre u y v está dada por: d(u,v) = t(v).

b) Pasos


1. Etiquete el nodo origen con etiqueta permanente 0
2. A partir delúltimo nodo i etiquetado con etiqueta permanente, determine la etiqueta temporal de cada nodo j (sin etiqueta permanente) conectado al nodo i mediante el arco (i,j) y la guía de ruta, de la siguiente manera:


Nueva etiqueta = min { etiqueta temporal actual de j ; etiqueta

temporal de j permanente de i + Lij}







Guía de ruta

[pic]3.La menor de todas las etiquetas temporales actuales se convierte en etiqueta permanente. Si hay empate se escoge cualquiera.

4.Volver al paso 2 hasta etiquetar el nodo destino con etiqueta permanente.




c) Análisis de la complejidad

En cada iteración se añade un vértice a T, luego el número de iteraciones es n. En cada una se elige una etiqueta mínima, la primera vez entren-1, la segunda entre n-2, ..., luego la complejidad total de estas elecciones es O(n2). Por otra parte cada arista da lugar a una actualización de etiqueta, que se puede hacer en tiempo constante O(1), en total pues O(q). Por tanto la complejidad total del algoritmo es O(n2).

d) Aplicaciones


1. Encaminamiento de paquetes por los routers:


Consideremos una red telefónica.En un momento dado, un mensaje puede tardar una cierta cantidad de tiempo en atravesar cada línea (debido a efectos de congestión, retrasos en las conexiones etc.). En este caso tenemos una red con costes en los arcos y dos nodos especiales: el nodo de comienzo y el de finalización, el objetivo aquí es encontrar un camino entre estos dos nodos cuyo coste total sea el mínimo.


2.Aplicaciones para Sistemas de información geográficos:


extracción de características curvilíneas de imágenes usando técnicas de minimización del camino [4]: La imagen se representa como una matriz de puntos, cada uno con una especial intensidad. Cada nodo se corresponde con un punto (pixel) de la imagen y tiene hasta ocho nodos adyacentes.


El peso de los arcos viene dado en este casopor la diferencia de intensidad. Esta técnica presenta un gran ahorro de costes frente a las herramientas existentes actualmente en el mercado que usan métodos de vectorización automáticos.








3. Caminos mínimos en Grafos usando XML y parsers de Java:


El concepto de camino es una secuencia de operadores y conectores: un operador será cualquier unidad de proceso de...