Algoritmo De Johnson

-------------------------------------------------
Algoritmo de Johnson
El algoritmo de Johnson es una forma de encontrar el camino más corto entre todos los pares de vértices de un grafo dirigido disperso. Permite que lasaristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicialque elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. Su nombre viene de Donald B. Johnson, quien fuera el primero en publicar la técnica en 1977.
-------------------------------------------------
Descripción del algoritmo
El algoritmo de Johnson consiste en los siguientes pasos:
1. Primero se añade un nuevo nodo q algrafo, conectado a cada uno de los nodos del grafo por una arista de peso cero.
2. En segundo lugar, se utiliza el algoritmo de Bellman-Ford, empezando por el nuevo vértice q, para determinara para cada vértice v el peso mínimo h(v)del camino de q a v. Si en este paso se detecta un ciclo negativo, el algoritmo concluye.
3. Seguidamente, a las aristas del grafo original se les cambia el pesousando los valores calculados por el algoritmo de Bellman-Ford: una arista de u a vcon tamaño w(u, v), da el nuevo tamaño w(u, v) + h(u) – h(v)
4. Por último, para cada nodo s se usa el algoritmo de Dijkstra para determinar el camino más corto entre s y los otros nodos, usando el grafo con pesos modificados.
En el grafo con pesos modificados, todos los caminos entre un par denodos s y t tienen la misma cantidad h(s) – h(t) añadida a cada uno de ellos, así que un camino que sea el más corto en el grafo original también es el camino más corto en el grafo modificado y viceversa. Sin embargo, debido al modo en el que los valores h(v) son computados, todos los pesos modificados de las aristas son no negativos, asegurando entonces la optimalidad de los caminos encontrados por el algoritmo deDijkstra. Las distancias en el grafo original pueden ser calculadas a partir de las distancias calculadas por el algoritmo de Dijkstra en el grafo modificado invirtiendo la transformación realizada en el grafo.
-------------------------------------------------
[editar]Análisis de la complejidad
La complejidad temporal de este algoritmo, usando montículos de Fibonacci en la implementacióndel algoritmo de Dijkstra, es de O(V2log V + VE): el algoritmo usa un tiempo de O(VE) para la fase Bellman-Ford del algoritmo, y O(V log V + E) para cada una de las V instancias realizadas del algoritmo de Dijkstra. Entonces, cuando el grafo es disperso el tiempo total del algoritmo puede ser menor que el algoritmo de Floyd-Warshall, que resuelve el mismo problema en un tiempo de O(V3).-------------------------------------------------
[editar]Ejemplo
Las etapas del algoritmo de Johnson están descritas en la siguiente ilustración: 
En la imagen de la izquierda tiene dos aristas negativas y no contiene ciclos negativos. En la segunda imagen se muestra el nuevo vértice q con peso 0 hacia todos los nodos. En la tercera imagen, se muestra el árbol de caminos mínimos calculado con el algoritmo deBellman-Ford con q como vértice inicial, y los valores h(v) calculados para cada otro nodo como la longitud del camino más corto entre q y ese nodo. A modo de ilustración, en dicha imagen solo aparecen los caminos que se tomarían para determinar cada valor h(v). Nótese que todos estos valores h(v) no son positivos, porque q tiene una arista de unión con cada nodo de peso 0, y por tanto el caminomás corto no puede ser mayor que ese valor. En la parte derecha se muestra el grafo modificado, hecho reemplazando el peso de cada arista w(u, v) por w(u, v) + h(u) – h(v). En este grafo modificado, todos los pesos de las aristas son positivos y el camino más corto entre dos nodos cualesquiera usa la misma secuencia de aristas que en el camino más corto entre los mismos dos nodos en el grafo...