mat_path.H File Reference

Path reconstruction from Floyd-Warshall path matrices. More...

#include <tpl_matgraph.H>

Include dependency graph for mat_path.H:

Go to the source code of this file.

Classes
class	Aleph::Find_Min_Path< Mat >
	Functor wrapper for find_min_path. More...

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

Functions
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.

Detailed Description

Path reconstruction from Floyd-Warshall path matrices.

This file provides utilities for reconstructing minimum paths from the path matrix computed by the Floyd-Warshall all-pairs shortest path algorithm.

Overview

After running Floyd-Warshall (see latex_floyd.H or Floyd_Warshall.H), you obtain two matrices:

• Distance matrix (dist): Contains the shortest path distances
• Path matrix (path): Contains intermediate node indices for path reconstruction

This file provides find_min_path() to reconstruct the actual path from the path matrix.

Path Matrix Interpretation

For a path from node i to node j:

• path(i, j) contains the index of the next node after i on the shortest path
• To reconstruct the full path: start at i, follow path(i, j), path(path(i,j), j), etc.

Usage Example

#include <mat_path.H>
#include <latex_floyd.H>
 
// Create adjacency matrix and run Floyd-Warshall
Ady_Mat<Graph, long, Max_Dist_Val> dist(graph);
Ady_Mat<Graph, long, Max_Dist_Val> path(graph);
floyd_all_shortest_paths(dist, path);
 
// Reconstruct path from node 0 to node 5
Path<Graph> min_path;
find_min_path(path, 0L, 5L, min_path);
 
// Or using node pointers
find_min_path(path, src_node, tgt_node, min_path);

See also

latex_floyd.H Floyd-Warshall algorithm with LaTeX output

Floyd_Warshall.H Standard Floyd-Warshall implementation

tpl_matgraph.H Matrix-based graph representations

Author

Leandro Rabindranath León

Definition in file mat_path.H.