ı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 Bellman-Ford : que es, definición y significado, descargar videos y fotos.

videos internet

salud  ıllı Algoritmo de Bellman-Ford : que es, definición y significado, descargar videos y fotos.  


El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford) produce el camino más corto en un grafo dirigido ponderado (en el que el peso de ciertas aristas puede ser negativo). El algoritmo de Dijkstra soluciona este inconveniente en un tiempo menor, mas requiere que los pesos de las aristas no sean negativos, a menos que el grafo sea dirigido y sin ciclos. Con lo que el Algoritmo Bellman-Ford en general se emplea cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.


Según Robert Sedgewick, “Los pesos negativos no son sencillamente una curiosidad matemática; brotan de una manera natural en la reducción a inconvenientes de caminos más cortos”, y son un caso de una reducción del inconveniente del camino hamiltoniano que es NP-completo hasta el inconveniente de caminos más cortos con pesos generales. Si un grafo contiene un ciclo de costo total negativo entonces este grafo no tiene solución. El algoritmo es capaz de advertir este caso.


Si el grafo contiene un ciclo de costo negativo, el algoritmo lo advertirá, mas no hallará el camino más corto que no repite ningún vértice. La dificultad de este inconveniente es cuando menos la del inconveniente del camino más largo de dificultad NP-Completo.



El Algoritmo de Bellman-Ford es, en su estructura básica, muy semejante al algoritmo de Dijkstra, mas en lugar de escoger vorazmente el nodo de peso mínimo incluso sin procesar para relajarlo, sencillamente relaja todas y cada una de las aristas, y lo hace |V|-1 veces, siendo |V| el número de vértices en el grafo. Las reiteraciones dejan a las distancias mínimas recorrer el árbol, puesto que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez. En contraste a la solución insaciable, la que depende de la suposición de que los pesos sean positivos, esta solución se acerca más al caso general.


Existen 2 versiones:



  • Versión no optimada para grafos con ciclos negativos, cuyo costo de tiempo es O(VE).
  • Versión optimada para grafos con aristas de peso negativo, mas en el grafo no existen ciclos de costo negativo, cuyo costo de tiempo, es asimismo O(VE).
bool BellmanFord(Grafo G, nodo_origen s)// iniciamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que// tiene distancia 0for v ? V do distancia=INFINITO predecesor=NULL distancia=0 // relajamos cada arista del grafo en tantas ocasiones como número de nodos -1 haya en el grafofor i=1 to |V|-1 dofor (o bien, v) ? E doif distancia>distancia + peso(o bien, v) then distancia = distancia + peso (o bien, v) predecesor = o bien // verificamos si hay ciclos negativofor (o bien, v) ? E do if distancia > distancia + peso(o bien, v) then print ("Hay ciclo negativo") return FALSE return TRUE
bool BellmanFord_Optimizado(Grafo G, nodo_origen s)// iniciamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que// tiene distancia 0. Para esto lo hacemos recorriéndonos todos y cada uno de los vértices del grafofor v ? V do distancia=INFINITO padre=NULL distancia=0 encolar(s, Q) en_cola=TRUE while Q!=0 then o bien = extraer(Q) en_cola=FALSE // relajamos las aristasfor v ? ady doif distancia>distancia + peso(o bien, v) then distancia = distancia + peso (o bien, v) padre = o bien if en_cola==FALSE then encolar(v, Q) en_cola=TRUE

Aplicaciones de encaminamiento


Una variación distribuida del Algoritmo del Bellman-Ford se utiliza en protocolos de encaminamiento basados en vector de distancias, por servirnos de un ejemplo el Protocolo de encaminamiento de información (RIP). El algoritmo es distribuido por el hecho de que envuelve una serie de nodos (enrutadores) en un Sistema autónomo(AS), un conjunto de redes y dispositivos enrutador IP administrados típicamente por un Distribuidor de Servicio de Internet (ISP). Se compone de los próximos pasos:



  1. Cada nodo calcula la distancia entre él mismo y todos los otros en un AS y guarda esta información en una tabla.
  2. Cada nodo manda su tabla a todos y cada uno de los nodos vecinos.
  3. Cuando un nodo recibe las tablas de distancias de sus vecinos, este calcula la senda más corta a el resto nodos y actualiza su tabla para reflejar los cambios.

Las desventajas primordiales del algoritmo de Bellman-Ford en este ajuste son:



  • No escala bien
  • Los cambios en la topología de red no se reflejan de manera rápida en tanto que las actualizaciones se distribuyen nodo por nodo.
  • Contando hasta el infinito(si un fallo de link o bien nodo hace que un nodo sea inaccesible desde un conjunto de otros nodos, estos pueden estar siempre y en toda circunstancia incrementando gradualmente sus cálculos de distancia a él, y mientras puede haber bucles de enrutamiento)

En mil novecientos setenta Yen describió una mejora del algoritmo Bellman-Ford para un grafo sin ciclos con peso negativo. Esta mejora primero asigna un orden arbitrario lineal a todos y cada uno de los vértices y después divide el conjunto de todas y cada una de las aristas en uno o bien 2 subconjuntos. El primer subconjunto, Ef, contiene todas y cada una de las aristas (vi,vj) semejantes que i < j; al paso que el segundo, Eb, contiene aristas (vi,vj) semejantes que i > j. Cada vértice se visita en orden v1,v2,…,v|v|, relajando cada arista saliente de ese vértice en Ef. Cada vértice es, después, visitado en orden v|v|,v|v-1|,…,v1, relajando cada arista saliente de ese vértice en Eb. La mejora de Yen reduce a la mitad, de forma eficaz, el número de “pases” requeridos para la solución del camino más corto desde una sola fuente.


Véase también



  • Richard Bellman: On a Routing Problem, in Quarterly of Applied Mathematics, 16(1), pp.87-noventa, mil novecientos cincuenta y ocho.
  • Lestor R. Ford jr., D. R. Fulkerson: Flows in Networks, Princeton University Press, mil novecientos sesenta y dos.
  • Thomas H. Cormen, Converses Y también. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, dos mil uno.ISBN 0-doscientos sesenta y dos-tres mil doscientos noventa y tres-siete. Section 24.1: The Bellman-Ford algorithm, pp.588–592.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmo de Bellman-Ford : que es, definición y significado, descargar videos y fotos.

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