software de sistemas

Algoritmo de la ruta más corta


El algoritmo de Dijkstra, concebida por el holandés equipo científico de DijkstraEdsger en 1956 y publicado en 1959, es un algoritmo de búsqueda gráfico que resuelve la sola fuente más corta problema del camino para un gráfico con los negativos de borde costos de ruta, produciendo un camino más corto árbol . Este algoritmo se utiliza a menudo en la ruta y como una subrutina en otros algoritmos de grafos. Para una fuente dada de vértice (nodo) en el gráfico, el algoritmo encuentra la ruta con menor coste (es decir, el camino más corto) entre el vértice y cualquier otro vértice. También puede ser utilizado para encontrar costos de caminos más cortos desde un vértice único a un destino único vértice al detener el algoritmo una vez que el camino más corto al destino vértice ha sido determinada. Por ejemplo, si los vértices de la gráfica representan las ciudades y los costos de borde de ruta representan conducir distancias entre pares de ciudades conectadas por un camino directo, el algoritmo de Dijkstra se puede utilizar para encontrar la ruta más corta entre una ciudad y todas las demás ciudades. Como resultado, el camino más corto primero es ampliamente utilizado en la red los protocolos de enrutamiento, en especial IS-IS y OSPF (Open ShortestPathFirst). Algoritmo original de Dijkstra no utiliza una cola de prioridad min y se ejecuta en


O


(|


V


|


2).


La idea de este algoritmo también se da en un ( Leyzorek et al. 1957 ). Apuesta en práctica común, basada en una cola de prioridad min-implementado por un montón de Fibonacci y se ejecuta en


O


(|


E


| + |


V


| Registro |


V


|) se debe a (Fredman y Tarjan 1984 ). Esto es asintóticamente más rápido de lo conocido de una sola fuente de camino más corto algoritmo para arbitrarios grafos dirigidos con pesos no negativos sin límites. (Para una visión general de los primeros algoritmos del camino más corto y las mejoras y adaptaciones posteriores, ver: una sola fuente de caminos más cortos de los algoritmos de grafos dirigidos con pesos no negativos.)Ilustración de búsqueda algoritmo de Dijkstra para encontrar ruta de acceso desde un nodo de inicio a un nodo meta en un robot de planificación de movimiento problema. Los nodos abiertos representan la "tentativa" de ajuste. Los nodos son visitados los rellenos, con el color que representa la distancia: cuanto más verde, más lejos. Los nodos en todas las diferentes direcciones se exploran de manera uniforme, apareciendo como más o menos circular de frente de onda como el algoritmo de Dijkstra utiliza una heurística idénticamente igual a 0.Deje que el nodo en el que estamos empezando ser llamado el nodo inicial. Quela distancia del nodo Y es la distancia desde el nodo inicial al algoritmo de DijkstraY. asignará algunos valores de la distancia inicial y trataremos de mejorar paso a paso.






CAMINO MAS CORTO: ALGORITMO DE DIJKSTRA



Para el problema de la ruta corta tenemos varios algoritmos, en esta oportunidad se explicará el algoritmo de dijkstra el cual usa una técnica voraz (greedy). Al final del articulo se encuentran adjuntas las implementaciones en C++ y JAVA.

Descripción

El algoritmo de dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:
Si los pesos de mis aristas son de valor 1, entonces bastará con usar elalgoritmo de BFS.
Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

Como trabaja

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 - La técnica greedy utiliza el principio de que para que un camino sea óptimo, todos los caminos que contiene también deben ser óptimos- 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 comorelajación (relaxation).

Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos una Cola de Prioridad o Heap, este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los nodos.

Tanto java como C++ cuentan con una cola de prioridad ambos implementan un Binary Heap aunque con un Fibonacci Heap la complejidad de dijkstra se reduce haciéndolo mas eficiente, pero en un concurso mas vale usar la librería que intentar programar una nueva estructura como un Fibonacci Heap, claro que particularmente uno puede investigar y programarlo para saber como funciona internamente.

Algoritmo en pseudocódigo

Considerar distancia[ i ] como la distancia mas corta del vértice origen ingresado al vértice i.1 método Dijkstra(Grafo,origen): 2 creamos una cola de prioridad Q 3 agregamos origen a la cola de prioridad Q 4 mientras Q no este vacío: 5 sacamos un elemento de la cola Q llamado u 6 si u ya fue visitado continuo sacando elementos de Q 7 marcamos como visitado u 8 para cada vértice v adyacente a u en el Grafo: 9 sea w el peso entre vértices ( u , v ) 10 si v no ah sido visitado: 11 Relajacion( u , v , w ) 1 método Relajacion( actual , adyacente , peso ): 2 si distancia[ actual ] + peso < distancia[ adyacente ] 3 distancia[ adyacente ] = distancia[ actual ] + peso 4 agregamos adyacente a la cola de prioridad Q


Ejemplo y Código paso a paso

Tengamos el siguiente grafo, cuyos ID están en color negro encima de cada vértice, los pesos esta en color azul y la distancia inicial en cada vértice es infinito



Algunas consideraciones para entender el código que se explicara junto con el funcionamiento del algoritmo.