latex_floyd.H File Reference

Floyd-Warshall algorithm with LaTeX output generation. More...

#include <ahFunction.H>
#include <tpl_matgraph.H>
#include <mat_latex.H>

Include dependency graph for latex_floyd.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Initialize_Dist< AM >
	Matrix initialization functor for Floyd-Warshall. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class GT , class Compare , class Plus >
void	Aleph::floyd_all_shortest_paths (GT &g, Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &dist, Ady_Mat< GT, long > &path)
	Compute all-pairs shortest paths using Floyd-Warshall algorithm.
template<class GT >
void	Aleph::floyd_all_shortest_paths (GT &g, Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &dist, Ady_Mat< GT, long > &path)
	Overload using default comparison (less) and addition (plus).
template<class Mat >
void	Aleph::find_min_path (Mat &p, const long src_index, const long tgt_index, Path< typename Mat::Graph_Type > &path)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Variant that accepts const indices.
template<class Mat >
void	Aleph::find_min_path (Mat &p, typename Mat::Node *src_node, typename Mat::Node *tgt_node, Path< typename Mat::Graph_Type > &path)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Reconstruct shortest path from path matrix using node pointers.
template<class GT , class Compare , class Plus , template< class > class P_i, template< class > class P_ij, template< class > class D_ij>
void	Aleph::floyd_all_shortest_paths_latex (GT &g, Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &dist, Ady_Mat< GT, long > &path, std::ofstream &output)
	Floyd-Warshall algorithm with LaTeX step-by-step output.
template<class GT , template< class > class P_i, template< class > class P_ij, template< class > class D_ij>
void	Aleph::floyd_all_shortest_paths_latex (GT &g, Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &dist, Ady_Mat< GT, long > &path, std::ofstream &output)
	Overload using default comparison (less) and addition (plus).

Detailed Description

Floyd-Warshall algorithm with LaTeX output generation.

This file provides the Floyd-Warshall all-pairs shortest path algorithm with optional LaTeX output that shows the distance and path matrices at each iteration step.

Algorithm Overview

Floyd-Warshall computes shortest paths between all pairs of vertices in O(V³) time and O(V²) space. It works with:

• Directed and undirected graphs
• Positive and negative edge weights (no negative cycles)

Key Components

• floyd_all_shortest_paths(): Core algorithm
• floyd_all_shortest_paths_latex(): Algorithm with LaTeX step-by-step output
• find_min_path(): Path reconstruction from the path matrix

Arc Type Requirements

The arc type GT::Arc_Type must provide:

• Type Distance_Type (e.g., int, double)
• Static constant Max_Distance (infinity value)
• Static constant Zero_Distance (identity for addition)
• Method get_distance() returning the arc weight

Usage Example

// Create distance and path matrices
Ady_Mat<Graph, double> dist(g);
Ady_Mat<Graph, long> path(g);
 
// Compute all shortest paths
floyd_all_shortest_paths(g, dist, path);
 
// Reconstruct a specific path
Path<Graph> p;
find_min_path(path, src_idx, tgt_idx, p);

See also

tpl_matgraph.H For adjacency matrix representation

mat_latex.H For LaTeX matrix formatting

Author

Leandro Rabindranath León

Definition in file latex_floyd.H.