Algoritmo de Dijkstra, El Problema de la Ruta más Corta

El Problema de la Ruta más Corta
Se refiere a una red en la que cada arco (i , j) tiene asociado un número cij que se interpreta como la distancia (costo o tiempo) que hay entre los vértices i y j. El objetivo consiste en encontrar las rutas más cortas (económicas, rápidas) entre un nodo específico y todos los demás nodos de la red.

Algoritmo de Dijkstra

Consiste en asignar una etiqueta a cada nodo de la red, la que luego de sucesivas actualizaciones, contendrá el valor del camino de valor mínimo que une el nodo incio de la red con el nodo considerado y el vértice precedente en dicho camino.

Para etiquetar cada uno de los nodos de la red se procede de la siguiente forma:

Paso 1: Considere todos los nodos que estén conectados con el origen por un arco, es decir a través de un camino de longitud 1. A cada uno de ellos se le colocará una etiqueta que tiene dos componentes a saber:

[ j , d ] dónde j representa el nodo precedente y d representa distancia.

El componente de distancia de la etiqueta que se pone en cada nodo de éstos es la distancia desde el origen. El otro componente es el nodo predecesor (el origen en este caso). Estas etiquetas serán temporales.

Paso 2: De todos los nodos con etiqueta temporal, se elige uno cuyo componente de distancia sea mínimo y se lo etiqueta permanente. Los empates se rompen arbitrariamente. Cuando todos los nodos son permanentes se pasa al Paso 4.

Paso 3: Todo nodo que no tenga actualmente etiqueta permanente, estará sin etiqueta o con una temporal. Si i es el último etiquetado permanente considere todos los vértices que estén conectados directamente con éste a través de un camino de longitud 1. Para cada uno de ellos calcular la suma de su distancia a i más la distancia de la etiqueta de i .

Si el nodo no está etiquetado darle una etiqueta temporal. Si el nodo en cuestión ya tiene etiqueta temporal, cambiarla sólo si la distancia recién calculada es menor que la componente de distancia de la etiqueta actual. Si la distancia recién calculada es igual a la que tiene la etiqueta anterior, conservar ambas. Regresar al Paso 2.

Paso 4: Las etiquetas permanentes indican la distancia más corta desde el origen a cada nodo de la red. También indican el nodo predecesor en la ruta más corta hacia cada nodo.

This entry was posted in Utilitarios. Bookmark the permalink.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>