La ruta más corta

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.

DEFINICIÓN DEL PROBLEMA

-Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.

-Arcos bi-direccionales conectan los nodos i y j con distancias mayores que cero, dij

-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:

Primer paso: Elaborar un cuadro con todos los nodos y los ramales que salen de él.

Segundo paso: Partiendo del origen, debemos encontrar el nodo más cercano a él.

Tercer paso: Anular todos los ramales que entren al nodo más cercano elegido.

Cuarto paso: Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino.

Algoritmo Acíclico:

Si la red no tiene ciclos, apliquemos el siguiente algoritmo:

Etiquetar cada nodo con el siguiente formato [distancia desde el nodo inicial, Nombre del Nodo Precedente]. Para el nodo inicial por definición la distancia es cero (la distancia a sí mismo), y el nodo precedente es vacío (ninguno): [0 , ] . Después para cada nodo, se analiza los nodos que lo preceden por las flechas, se escoge aquel cuya distancia al nodo inicial más la distancia al nodo presente sea mínima. Se etiqueta con la suma, y el nombre del nodo escogido... bueno, esto en carreta es muy enredador... mejor con un ejemplo, paso a paso.

Consideremos la siguiente red:

Los nodos pueden representan sitios (p.e ciudades, facilidades, etc) las flechas (también llamadas Arcos) indican las trayectorias permitidas y sobre ellas están las distancias (pero también puede representar el costo de desplazamiento, o el nivel de riesgo, o un producto de ambos).

Encontremos la distancia más corta entre el nodo "A" y el nodo "G".

1. Rotular el Nodo Inicial : Recordemos el formato del rótulo es : [distancia al primer nodo, nodo precedente]. La distancia al primer nodo, es la distancia a sí mismo en éste caso, por lo tanto es cero. El nodo precedente: como no viene de ningún nodo, lo rotulamos vacio: [ 0, ] :

  

2. Rotular todos los nodos que dependan únicamente del nodo inicial:

A el Nodo B se puede llegar desde el Nodo A, con la ruta A-C-B o con la ruta A-D-C-B. Así que depende de otros nodos a parte del Nodo inicial. Lo mismo podemos decir del Nodo C. Pero...

... Pero al Nodo D sólo se puede llegar directamente desde el Nodo A. Este es el nodo que vamos a rotular, y si hubieran más como él también los regalariamos, pero en este ejemplo sólo tenemos el D.

El rótulo del Nodo D, es : [distancia mínima desde el Nodo Inicial, Nodo Precedente]. La distancia mínima desde el Nodo Inicial al Nodo D es 15: pos no hay otra alternativa, che! y el Nodo Precedente el "A". Rótulo: [15, "A"]

    

3. Rotular Todos los Nodos que tengan la información suficiente para rotularlos:

La información necesaria para rotular un Nodo con este algoritmo, es que todos los Nodos de los que dependa, deben estar ya rotulados. Por ejemplo el Nodo B: depende del A y del C. El Nodo A ya esta rotulado, pero el C aún no. Así que aún no se puede rotular el Nodo B. El Nodo C depende del A y del D, y ambos están rotulados, así que si podemos rotularlo. La distancia desde A es 8, y desde D es: la distancia que tiene en el rótulo (que es la distancia mínima desde él al Nodo inicial, o sea 15), MAS la distancia entre D y C = 15 +4 = 19: entre 8 y 19 es más pequeño 8. Así que escogemos el Nodo A como precedente: el rótulo es [ 8 , "A"]

  

4. Seguir rotulando todos los Nodos que tengan información suficiente hasta llegar al Nodo deseado:

G. Ahora ya hay información suficiente para rotular los Nodos B y F. Entonces rotulemos el Nodo B (no importa cuál se haga primero, igual hay que rotularlos todos). El rotulo para el Nodo B: La distancia desde A es 10, la distancia mínima al Nodo inicial desde C es: el la distancia del rótulo de C: 8 + la distancia de C a B : 3 => 8 + 3 = 11. El mínimo entre 10 y 11 es 10. Rótulo= [10, "A"].

  

Rótulo para el F: Desde C : 8 + 4 = 12 y desde D : 15 + 15 = 30. Entonces el Rótulo es [12, "C" ]

  

Rótulo para el Nodo E: Desde B : 10 + 20 = 30 y desde C: 8 + 15 = 23 Rótulo : [23,"C"]

Por último para el Nodo G: la distancia desde E es 23 + 5 = 28 y desde F es 12 + 3 = 15 Rótulo [15, F]

  

Ahora se puede leer la trayectoria mínima partiendo del rótulo del Nodo G, dicho rotulo nos dice que viene del F el de F dice que viene del C y el del C dice que viene del A. Solución: Distancia Mínima= 15 Ruta Más Corta = A-C-F-G

Ejemplo en video