Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA > Class Template Reference

#include <Floyd.H>

Public Member Functions
bool	has_negative_cycle () const noexcept
const DynMatrix< long > &	get_path_mat () const noexcept
const DynMatrix< Distance_Type > &	get_dist_mat () const noexcept
const DynArray< Node * >	get_nodes () const noexcept
Node *	select_node (long i) const noexcept
long	index_node (Node *p) const noexcept
	Floyd_All_Shortest_Paths (const GT &__g, SA &__sa)
	Floyd_All_Shortest_Paths (const GT &g, SA &&sa=SA())
string	entry (const Distance_Type &e)
Path< GT >	get_min_path (const long src_idx, const long tgt_idx) const
Path< GT >	get_min_path (typename GT::Node *src, typename GT::Node *tgt) const

Static Public Member Functions
static void	print (DynMatrix< Distance_Type > &dist)

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
class Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >

Calcula las matriz de costes de los caminos mínimos entre todos pares de nodos de un grafo g y la matriz de caminos mínimos según el algoritmo de Floy-Warshall.

Esta clase utiliza el algoritmo de Floy-Warshall para calcular dos matrices de tipo Ady_Mat que se especifican del siguiente modo:

1. dist: matriz de costes mínimos entre todos los pares de nodos. Cada entrada dist(i,j) almacena el coste total mínimo para ir del nodo con índice i hacia el nodo con índice j.
   Recuérdese que un índice de nodo en la matriz dist puede calcularse mediante dist(node), donde node es un puntero a nodo en una representación con listas enlzadas derivada del tipo de grafo
2. path: matriz de caminos mínimos. Cada entrada path(i,j) almacena el nodo k que permitió al algoritmo de Floyd-Warshall encontrar el mínimo valor de dist(i,j). De este modo, inspecciones sucesivas a dist(k,j) permiten encontrar y construir el camino hacia el nodo j.
   La función find_min_path(g,i,j,path) realiza la función anterior.

El algoritmo de Floyd-Warshall maneja pesos negativos, pero no opera correctamente si el grafo contiene ciclos negativos. Úsese el algoritmo de Bellman-Ford q_bellman_ford_min_spanning_tree() si se sospecha su presencia.

El algoritmo utiliza dos matrices internas adicionales.

El procedimiento es parametrizado con las siguientes especificaciones:

1. GT: el tipo de grafo
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. SA: filtro de arcos.

See also

dijkstra_min_spanning_tree() dijkstra_min_path() find_path_depth_first() find_min_path() bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Member Function Documentation

index_node()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

long Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::index_node ( Node *  p ) const

inlinenoexcept

Retorna el ìndice dentro de una matriz de adyacencia que tendría el nodo p

Here is the call graph for this function:

select_node()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

Node* Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::select_node ( long  i ) const

inlinenoexcept

Retorna el nodo correspondiente al índice i en una matriz de adyacencia para el algoritmo de Floyd-Warshall

---

The documentation for this class was generated from the following file:

• Floyd.H