algoritmo de Belmart
Páginas: 4 (779 palabras)
Publicado: 27 de octubre de 2013
2. ALGORITMO DE BELMAN-FOR
CAMINO MAS CORTO: ALGORITMO DE BELLMAN-FOR
El objetivo del Algoritmo es encontrar el camino mínimo desde todos los nodos al vérticeE, El algoritmo deBellman-Ford determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. La diferencia de este algoritmo con los demás es quelos pesos pueden tener valores negativos ya que Bellman-Ford me permite detectar la existencia de un ciclo negativo.
El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, perorequiere 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
Si el grafo contiene un ciclo de coste negativo,el algoritmo lo detectará pero no encontrará el camino más corto que no repite ningún vértice, la complejidad de este problema es NP-completo.
COMO TRABAJA
El algoritmo parte de un vértice origenque será ingresado, a diferencia de Dijkstra que utiliza una técnica voraz para seleccionar vértices de menor peso y actualizar sus distancias mediante el paso de relajación, Bellman-Ford simplementerelaja todas las aristas y lo hace |V| – 1 veces, siendo |V| el número de vértices del grafo.
Para la detección de ciclos negativos realizamos el paso de relajación una vez más y si se obtuvieronmejores resultados es porque existe un ciclo negativo, para verificar porque tenemos un ciclo podemos seguir relajando las veces que queramos y seguiremos obteniendo mejores resultados.
EXPLICACIÓN DELALGORITMO
En el paso 0, inicializamos todas las distancias o costos mínimos a infinito.
En el paso 1, actualizamos el paso anterior, aplicando las fórmulas. En este caso ponemos la distancia de losnodos que tienen accesos directos al vértice 1, y se la sumamos a la distancia mínima acumulada que hay hasta el vértice oportuno. Aquí esta distancia acumulada sería 0 para 1, debido que sería la...
2. ALGORITMO DE BELMAN-FOR
CAMINO MAS CORTO: ALGORITMO DE BELLMAN-FOR
El objetivo del Algoritmo es encontrar el camino mínimo desde todos los nodos al vérticeE, El algoritmo deBellman-Ford determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. La diferencia de este algoritmo con los demás es quelos pesos pueden tener valores negativos ya que Bellman-Ford me permite detectar la existencia de un ciclo negativo.
El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, perorequiere 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
Si el grafo contiene un ciclo de coste negativo,el algoritmo lo detectará pero no encontrará el camino más corto que no repite ningún vértice, la complejidad de este problema es NP-completo.
COMO TRABAJA
El algoritmo parte de un vértice origenque será ingresado, a diferencia de Dijkstra que utiliza una técnica voraz para seleccionar vértices de menor peso y actualizar sus distancias mediante el paso de relajación, Bellman-Ford simplementerelaja todas las aristas y lo hace |V| – 1 veces, siendo |V| el número de vértices del grafo.
Para la detección de ciclos negativos realizamos el paso de relajación una vez más y si se obtuvieronmejores resultados es porque existe un ciclo negativo, para verificar porque tenemos un ciclo podemos seguir relajando las veces que queramos y seguiremos obteniendo mejores resultados.
EXPLICACIÓN DELALGORITMO
En el paso 0, inicializamos todas las distancias o costos mínimos a infinito.
En el paso 1, actualizamos el paso anterior, aplicando las fórmulas. En este caso ponemos la distancia de losnodos que tienen accesos directos al vértice 1, y se la sumamos a la distancia mínima acumulada que hay hasta el vértice oportuno. Aquí esta distancia acumulada sería 0 para 1, debido que sería la...
Leer documento completo
Regístrate para leer el documento completo.