ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmo de Johnson wiki: info, historia y vídeos

videos internet

salud  Algoritmo de Johnson 


El algoritmo de Johnson es una forma de localizar el camino más corto entre todos y cada uno de los pares de vértices de un grafodirigidodisperso. Deja que las aristas tengan pesos negativos, aunque no deja ciclos de peso negativo. Marcha usando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que suprime todas y cada una de las aristas de peso negativo, dejando por consiguiente emplear 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 mil novecientos setenta y siete.



Descripción del algoritmo


El algoritmo de Johnson consiste en los próximos pasos:



  1. Primero se agrega un nuevo nodoq al grafo, conectado a cada uno de ellos de los nodos del grafo por una arista de peso cero.
  2. En segundo sitio, se emplea el algoritmo de Bellman-Ford, comenzando por el nuevo vértice q, para determinase para cada vértice v el peso mínimo h(v) del camino de q a v. Si en este paso se advierte un ciclo negativo, el algoritmo concluye.
  3. Seguidamente, a las aristas del grafo original se les cambia el peso empleando los valores calculados por el algoritmo de Bellman-Ford: una arista de o bien a v con tamaño w(o bien, v), da el nuevo tamaño w(o bien, v) + h(o bien) – h(v)
  4. Por último, para cada nodo s se emplea el algoritmo de Dijkstra para determinar el camino más corto entre s y los otros nodos, empleando el grafo con pesos cambiados.

En el grafo con pesos cambiados, todos y cada uno de los caminos entre dos nodos s y t tienen exactamente la misma cantidad h(s) – h(t) añadida a cada uno de ellos de ellos, con lo que un camino que sea el más corto en el grafo original asimismo es el camino más corto en el grafo cambiado y a la inversa. No obstante, debido al modo en el que los valores h(v) son computados, todos y cada uno de los pesos cambiados de las aristas son no negativos, asegurando entonces la optimalidad de los caminos encontrados por el algoritmo de Dijkstra. Las distancias en el grafo original pueden ser calculadas desde las distancias calculadas por el algoritmo de Dijkstra en el grafo cambiado invirtiendo la transformación efectuada en el grafo.


Análisis de la complejidad


La dificultad temporal de este algoritmo, empleando montículos de Fibonacci en la implementación del algoritmo de Dijkstra, es de O(V2log V + VE): el algoritmo utiliza un tiempo de O(VE) para la fase Bellman-Ford del algoritmo, y O(V log V + Y también) para cada una de las V instancias efectuadas del algoritmo de Dijkstra. Entonces, cuando el grafo es desperdigado el tiempo total del algoritmo puede ser menor que el algoritmo de Floyd-Warshall, que soluciona exactamente el mismo inconveniente en un tiempo de O(V3).


Las etapas del algoritmo de Johnson están descritas en la próxima ilustración:


En la imagen de la izquierda tiene 2 aristas negativas y no contiene ciclos negativos. En la segunda imagen se muestra el nuevo vértice q con peso 0 cara todos y cada uno de los nodos. En la tercera imagen, se muestra el árbol de caminos mínimos calculado con el algoritmo de Bellman-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. Como ilustración, en tal 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, pues q tiene una arista de unión con cada nodo de peso 0, y por ende el camino más corto no puede ser mayor que ese valor. En la parte derecha se muestra el grafo cambiado, hecho sustituyendo el peso de cada arista w(o bien, v) por w(o bien, v) + h(o bien) – h(v). En este grafo cambiado, todos y cada uno de los pesos de las aristas son positivos y el camino más corto entre 2 nodos cualquiera utiliza exactamente la misma secuencia de aristas que en el camino más corto entre ellos 2 nodos en el grafo original. El algoritmo concluye aplicando el algoritmo de Dijkstra para cada uno de ellos de los 4 nodos originales en el grafo cambiado (cuarta imagen).


Implementación


La estructura de datos para guardar el grafo consiste en una representación de cada vértice como una lista de las aristas que parten del mismo. Estas aristas constan de un origen, un destino y un peso. El conjunto de vértices se representa como un array de vértices y un índice que nos señala el último vértice empleado del array.


La implementación del algoritmo devuelve una matriz de elementos precedentes y otra de distancias, a través de la primera se puede continuar el camino de menor costo desde un nodo dado a cualquier otro nodo del grafo, y si en paralelo vamos sumando las distancias de la otra matriz, conseguimos los costos totales de tales caminos mínimos.

Tipos Arista = REGISTRO o bien : NATURAL d : NATURAL peso : INT sig : NATURAL FIN LAristas = PUNTERO A Arista TGrafo = ARRAY DE LAristas THv = ARRAY DE ENTERO TVector = ARRAY DE ENTERO TMatriz = ARRAY DE TVector
//suponemos ig>1 PROC Johnson (?grafo: TGrafo; ?ig: NATURAL; ? distancias: TMatriz ; ? previos: TMatriz) VARIABLES i : NATURAL p : LAristas min_caminos : THv aux_dist, aux_prev : TVector INICIO grafo? nueva_arista(ig,1,0,NULO) inc(ig) p ? grafoPARA i ? dos HASTA ig-dos HACER p^.sig ? nueva_arista(ig,i,0,NULO) p ? p^.sig FIN BellmanFord(grafo,ig, min_caminos) PARA i ? 1 HASTA ig-1 HACER p ? grafoMIENTRAS (p != NULO) HACER p^.peso ? p^.peso + min_caminos- min_caminosp ? p^.sig FINFINPARA i ? 1 HASTA ig-dos HACER Dijkstra(grafo,i, aux_dist,aux_prev) // devuelve los caminos mínimos desde el último nodo // a todos los otros previos? aux_prev; CalcularDistancias(grafo, anteriores, aux_dist,distancias); // este algoritmo efectúa la transformación inversa a la // que habíamos hecho ya antes sobre los pesos, para conseguir // las distancias reales FINFIN
#include<cstdlib>usingnamespacestd;structArista;typedefLAristasArista*;typedefTGrafoLAristatypedefTVectorinttypedefTMatrizTVector//suponemos ig>1voidjohnson(constTGrafo&grafo,intig,TMatriz&distancias,TMatriz&previos){Arista*p;TVectormin_caminos;TVectoraux_dist;TVectoraux_prev;grafonueva_arista(ig,1,0,NULL);ig++;p=grafofor(unsignedi=2;i<=ig-2;i++)BellmanFord(grafo,ig,min_caminos);for(unsignedi=1;i<=ig-1;i++)for(unsignedi=1;i<=ig-2;i++){Dijkstra(grafo,i-1,aux_dist,aux_prev)// devuelve los caminos mínimos desde el último nodo// a todos los otros.previosaux_prev;CalcularDistancias(grafo,previos,aux_dist,distancias);// este algoritmo efectúa la transformación inversa a la// que habíamos hecho ya antes sobre los pesos, para obtener// las distancias reales}}

La implementación más conveniente del algoritmo de Dijkstra sería a través de montículos, en tanto que es capaz de dar los mejores resultados a fin de que exactamente el mismo algoritmo de Johnson sea más eficaz.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmo de Johnson wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas