Algoritmo de Bellman ford
Para poder tomar el tema de esta clase de algoritmos, es necesario poder prestar atención a lo que se denomina como, TEORIA DE GRAFOS, la misma nos enseñara a manipular el orden de distintos procesos a efectuar.
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
mas info en...http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
Para comenzar debemos tener bien definido que el algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo).
Si entendemos bien dicho concepto, entonces podemos decir que el algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.
Este tipo de algoritmo eran originales de ruteo de la ARPANET. Su modo de funcionamiento es el siguiente:
Para poder tomar el tema de esta clase de algoritmos, es necesario poder prestar atención a lo que se denomina como, TEORIA DE GRAFOS, la misma nos enseñara a manipular el orden de distintos procesos a efectuar.
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
mas info en...http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
Para comenzar debemos tener bien definido que el algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo).
Si entendemos bien dicho concepto, entonces podemos decir que el algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.
Este tipo de algoritmo eran originales de ruteo de la ARPANET. Su modo de funcionamiento es el siguiente:
- Cada ruteador mantiene una tabla (un vector) que almacena las mejores distancias conocidas a cada destino y las líneas a usar para cada destino. Se actualizan las tablas intercambiando información con los vecinos.
- La tabla de un ruteador almacena una entrada para cada uno de los ruteadores en la subred (los ruteadores son los índices). Las entradas almacenan la línea preferida de salida y una estimación del tiempo o la distancia al destino. Se pueden usar métricas distintas (saltos, retrasos, etc.).
- Cada ruteador tiene que medir las distancias a sus vecinos. Por ejemplo, si la métrica es el retraso, el ruteador la puede medir usando paquetes de eco.
- Cada T msegs los ruteadores intercambian sus tablas con sus vecinos. Un ruteador usa lastablas de sus vecinos y sus mediciones de las distancias a sus vecinos para calcular una nueva tabla.
A modo de finalizar, la siguiente imagen, muestra el analisis grafico de un grafo aplicado en los canales de Venecia
:D
ResponderEliminar