Referencia de la plantilla de la Clase Aleph::Q_Bellman_Ford_Min_Spanning_Tree< GT, Distance, Compare, Plus, SA >

#include <Bellman_Ford.H>

Métodos públicos
bool	operator() (GT &g, typename GT::Node *start_node, GT &tree)
bool	has_negative_cycle (GT &g, typename GT::Node *s, Path< GT > &path) const

Descripción detallada

template<class GT, class Distance, class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
class Aleph::Q_Bellman_Ford_Min_Spanning_Tree< GT, Distance, Compare, Plus, SA >

Calcula un árbol abarcador de todos los caminos mínimos desde un nodo según el algoritmo de Bellman-Ford mejorado.

La clase utiliza el algoritmo mejorado de Bellman-Ford para calcular el árbol abarcador de todos los caminos mínimos desde un nodo de inicio.

El árbol abarcador resultante se mapea con el grafo original. De modo que una búsqueda de camino en profundidad, mediante find_path_depth_first() sobre el árbol, permite encontrar y construir cualquier camino mínimo desde el nodo de inicio hasta un nodo cualquiera.

Aunque el algoritmo de Bellman-Ford exhibe infierio desempeño que el de Dijkstra, el primero maneja pesos negativos y detecta la presencia de ciclos negativos. Es por tanto el algoritmo recomendado para la mayoría de aplicaciones de caminos s que manejen pesos negativos.

La clase se parametriza con las siguientes especificaciones:

1. GT: el tipo de grafo basado en List_Graph.
2. Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
   1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
   2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
   3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
   4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
3. Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
   • bool operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
4. Plus<GT>: clase que realiza la suma de distancias con el siguiente prototipo:
   • typename Distance<GT>::Distance_Type operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
5. SA: filtro de arcos.

Ver también

dijkstra_min_path() find_path_depth_first() floyd_all_shortest_paths() find_min_path() dijkstra_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Documentación de las funciones miembro

template<class GT , class Distance , class Compare , class Plus , class SA >

bool Aleph::Q_Bellman_Ford_Min_Spanning_Tree< GT, Distance, Compare, Plus, SA >::has_negative_cycle ( GT &  g, typename GT::Node *  s, Path< GT > &  path  ) const

inline

Determina si existe o no un ciclo negativo. En caso afirmativo se calcula.

Parámetros

[in]	g	el grafo sobre el cual buscar el ciclo negativo.
[in]	s	el nodo inicio desde el cual se desea calcular todos los caminos mínimos.
[out]	path	camino donde se guarda el ciclo.

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>

bool Aleph::Q_Bellman_Ford_Min_Spanning_Tree< GT, Distance, Compare, Plus, SA >::operator() ( GT &  g, typename GT::Node *  start_node, GT &  tree  )

inline

Invoca al cálculo del árbol de caminos mínimos según el algoritmo de Bellman-Ford.

Parámetros

[in]	g	el grafo al cual se desea calcular el árbol abarcador mínimo.
[in]	start_node	nodo inicio de los caminos mínimos.
[out]	tree	el grafo donde se desea guardar el árbol abarcador resultado de todos los caminos mínimos que parten desde el nodo start_node. Este grafo es limpiado antes del comienzo del algoritmo.

Devuelve

false si el grafo no tiene ciclos negativos. De lo contrario, se retorna true

Excepciones

bad_alloc

si no hay suficiente memoria para construir tree; bien sea porque falla tree o por la cola interna. En este caso el valor de tree es indeterminado y no está limpio.

---

La documentación para esta clase fue generada a partir del siguiente fichero:

• Bellman_Ford.H