1 2

35

4 15

30

20

25

50

45

10

25

4055

s t

a c

b d2

3 3

41

23

2

Algoritmos de caminos más cortos

CAMINOS CORTOSEn la Teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa.

En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.

CAMINOS CORTOS-GENERALIZACION• El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen “v” a todos los demás vértices del grafo.

•El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.

•El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo.

s t

a c

b d2

3 3

41

23

2

ALGORITMOS•Algoritmo de Dijkstra, resuelve el problema de los caminos más cortos desde un único vértice origen hasta todos los otros vértices (no negativos) del grafo.

•Algoritmo de Bellman - Ford, resuelve el problema de los caminos más cortos desde un origen si la ponderación de las aristas es negativa

•Algoritmo de Búsqueda A*, resuelve el problema de los caminos más cortos entre un par de vértices usando la heurística para intentar agilizar la búsqueda.

•Algoritmo de Floyd - Warshall, resuelve el problema de los caminos más cortos entre todos los vértices.

s t

a c

b d2

3 3

41

23

2

ALGORITMO DE DIJKSTRALa 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).

s t

a c

b d2

3 3

41

23

2

¿COMO FUNCIONA?Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado. A partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy (voraz)  entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no  utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias  tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).

¿COMO FUNCIONA?

¿COMO FUNCIONA?

¿COMO FUNCIONA?

Vemos que la distancia actual desde el vértice inicial a 2 es ∞, verifiquemos el paso de relajación:distancia[ 1 ] + 7 < distancia[ 2 ]      ->       0 + 7 < ∞        ->         7 < ∞El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 2 y agregando el vértice en la cola de prioridad con nueva distancia quedando:

¿COMO FUNCIONA?

¿COMO FUNCIONA?

De manera similar al anterior vemos que la distancia actual desde el vértice inicial a 4 es ∞, verifiquemos el paso de relajación:distancia[ 1 ] + 2 < distancia[ 4 ]      ->      0 + 2 < ∞        ->        2 < ∞El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 4 quedando:

¿COMO FUNCIONA?

En cuanto a la cola de prioridad como tenemos un vértice con menor pesoeste nuevo vértice ira en el tope de la cola:

¿COMO FUNCIONA?Revisamos sus adyacentes no visitados que serian vértices 2, 3 y 5.Empecemos por el vértice 2

Ahora vemos que la distancia actual del vértice inicial al vértice 2 es 7,verifiquemos el paso de relajación:distancia[ 4 ] + 3 < distancia[ 2 ]      ->      2 + 3 < 7         ->         5 < 7En esta oportunidad hemos encontrado una ruta mas corta partiendo desdeel vértice inicial al vértice 2, actualizamos la distancia en el vértice 2 yactualizamos el vértice previo al actual quedando:

¿COMO FUNCIONA?

En cuanto a la cola de prioridad como tenemos un vértice con menor pesoeste nuevo vértice ira en el tope de la cola, podemos ver que tenemos 2veces el mismo vértice pero como usamos una técnica greedysiempre usaremos el valor óptimo:

¿COMO FUNCIONA?Continuamos con los Vértices 3 y 5 como tienen valor ∞ si será posible relajarlos por lo que sería similar a los pasos iniciales solo que en los pasosiniciales distancia[ 1 ] era 0 en este caso distancia[ 4 ] es 2, quedando:

¿COMO FUNCIONA?Hemos terminado de evaluar al vértice 4, continuamos con el tope de lacola que es vértice 2, el cual marcamos como visitado.

Los adyacentes no visitados del vértice 2 son los vértices 3 y 5.Comencemos con el vértice 3

¿COMO FUNCIONA?

Ahora vemos que la distancia actual del vértice inicial al vértice 3 es 10, verifiquemos el paso de relajación:distancia[ 2 ] + 1 < distancia[ 3 ]      ->      5 + 1 < 10         ->         6 < 10En esta oportunidad hemos encontrado una ruta mas corta partiendo desde el vértice inicial al vértice 3, dicha ruta sería 1 -> 4 -> 2 -> 3 cuyo peso es 6 que es mucho menor que la ruta 1 – > 4 -> 3 cuyo peso es 10, actualizamos la distancia en el vértice 3 quedando:

¿COMO FUNCIONA?

El siguiente vértice de la cola de prioridad es el vértice 3 y su único adyacente no visitado es el vértice 5.

¿COMO FUNCIONA?

Vemos que la distancia actual del vértice inicial al vértice 5 es 7, verifiquemos el paso de relajación:distancia[ 3 ] + 5 < distancia[ 5 ]      ->      6 + 5 < 7         ->         11 < 7En esta oportunidad se no cumple por lo que no relajamos el vértice 5, por lo que la tabla en cuanto a distancias no sufre modificaciones y no agregamos vértices a la cola:

¿COMO FUNCIONA?

Ahora tocaría el vértice 2 pero como ya fue visitado seguimos extrayendo elementos de la cola, el siguiente vértice será el 5.

¿COMO FUNCIONA?Al ser el ultimo vértice a evaluar no posee adyacentes sin visitar por lo tanto hemos terminado el algoritmo. En el grafico anterior observamos que 2 aristas no fueron usadas para la relajación, las demás si fueron usadas. La tabla final quedaría de la siguiente manera:

De la tabla si deseo saber la distancia mas corta del vértice 1 al vértice 5, solo tengo que acceder al valor del arreglo en su índice respectivo (distancia[ 5 ]).

APLICACIONES DEL ALGORITMOLas aplicaciones del algoritmo de Dijkstra son muy diversas y de gran importancia en distintas áreas del conocimiento. Vamos a presentaralgunas de ellas.

Encaminamiento de paquetes por los routers : Consideremos una red telefónica. En un momento dado, un mensaje puede tardar unacierta 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 encontrarun camino entre estos dos nodos cuyo coste total sea el mínimo.

APLICACIONES DEL ALGORITMOAplicaciones 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: La imagen se representa como una matriz de puntos, cadauno 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 caso por la diferencia de intensidad. Esta técnica presenta un gran ahorro de costes frente a lasherramientas existentes actualmente en el mercado que usan métodos de vectorización automáticos.

Reconocimiento de lenguaje hablado: Un problema que se presenta es el distinguir entre palabras que suenan de manera similar.Se puede construir un grafo cuyos vértices correspondan a palabras posibles y cuyos arcos unan palabras que puedan ir colocadas una al lado de otra. Si el peso del arco corresponde a la probabilidad de que esténasí colocadas, el camino más corto en el grafo será la mejor interpretación de la frase.