Algoritmos

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es unalgoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos queparten 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 coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidosde la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
Índice
  [ocultar] 
1 Algoritmo
2 Complejidad
3 Pseudocódigo
4 Otra versión en pseudocódigo sin cola de prioridad
5 Implementación
5.1 C++
6 Véase también
7 Enlaces externos
Algoritmo[editar · editar código]
Teniendo un grafo dirigido ponderado de N nodosno aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremostodos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos nodos no marcados vi.
4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
5. Marcamos como completo el nodo a.
6. Tomamos como próximonodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
Complejidad[editar · editar código]
Orden de complejidad del algoritmo: O(|V|2+|E|) = O(|V|2) sin utilizar cola de prioridad, O((|E|+|V|) log |V|) utilizando cola de prioridad(por ejemplo un montículo).
Podemos estimar la complejidad computacional del algoritmo de Dijkstra (en términos de sumas y comparaciones). El algoritmo realiza a lo más n-1 iteraciones, ya que en cada iteración se añade un vértice al conjunto distinguido. Para estimar el número total de operaciones basta estimar el número de operaciones que se llevan a cabo en cada iteración. Podemos identificar elvértice con la menor etiqueta entre los que no están en Sk realizando n-1 comparaciones o menos. Después hacemos una suma y una comparación para actualizar la etiqueta de cada uno de los vértices que no están en Sk. Por tanto, en cada iteración se realizan a lo sumo 2(n-1) operaciones, ya que no puede haber más de n-1 etiquetas por actualizar en cada iteración. Como no se realizan más de n-1iteraciones, cada una de las cuales supone a lo más 2(n-1) operaciones, llegamos al siguiente teorema.
TEOREMA: El Algoritmo de Dijkstra realiza O(n2) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.
Pseudocódigo[editar · editar código]
Estructura de datos auxiliar: Q =Estructura de datos Cola de prioridad (se puede implementar con un montículo)
DIJKSTRA (Grafo G, nodo_fuente s)
para u ∈ V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
distancia[s] = 0
adicionar (cola, (s,distancia[s]))
mientras que cola no es vacía hacer
u = extraer_minimo(cola)
para todos v ∈ adyacencia[u]...