Floyd_Warshall.H File Reference

Floyd-Warshall algorithm for all-pairs shortest paths. More...

#include <sstream>
#include <iostream>
#include <limits>
#include <ahFunction.H>
#include <ahSort.H>
#include <tpl_indexArc.H>
#include <tpl_dynMat.H>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>
#include <ah-errors.H>

Include dependency graph for Floyd_Warshall.H:

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

Go to the source code of this file.

Classes
class	Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >
	Compute the all-pairs shortest path distance matrix and the path reconstruction matrix for a graph g using the Floyd-Warshall algorithm. More...

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

Detailed Description

Floyd-Warshall algorithm for all-pairs shortest paths.

This file implements the Floyd-Warshall algorithm, a dynamic programming approach to compute the shortest paths between all pairs of vertices in a weighted graph.

Algorithm Overview

Floyd-Warshall works by iteratively improving path estimates. For each intermediate vertex k, it checks if going through k provides a shorter path between any pair (i, j).

Key Features

• Computes shortest paths between ALL pairs of vertices
• Handles negative edge weights (but not negative cycles)
• Returns both distance matrix and path reconstruction matrix
• Can detect negative cycles (diagonal becomes negative)

Complexity

Metric	Value
Time	O(V³)
Space	O(V²) for matrices

When to Use

• Dense graphs where you need all-pairs distances
• Small to medium graphs (V < 1000)
• When negative weights are present (but no negative cycles)

For sparse graphs or single-source queries, consider:

• Dijkstra (single-source, no negative weights)
• Bellman-Ford (single-source, with negative weights)
• Johnson (all-pairs, sparse graphs with negative weights)

Usage Example

List_Graph<Node, Arc> g;
// ... build graph ...
 
Floyd_All_Shortest_Paths<decltype(g)> floyd(g);
floyd.compute();
 
// Get distance between nodes i and j
auto dist = floyd.get_dist(node_i, node_j);
 
// Reconstruct path
Path<Graph> path = floyd.get_min_path(node_i, node_j);

See also

Dijkstra.H For single-source shortest paths

Bellman_Ford.H For negative weight handling

Johnson.H For sparse all-pairs with negative weights

Author

Leandro Rabindranath León

Definition in file Floyd_Warshall.H.