write_floyd.C File Reference

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

#include <limits>
#include <iostream>
#include <tpl_matgraph.H>
#include <mat_latex.H>
#include <tpl_graph_utils.H>
#include <latex_floyd.H>

Include dependency graph for write_floyd.C:

Go to the source code of this file.

Classes
struct	C_i< M >
struct	C_ij< M >
struct	Di_ij< M >
struct	Nodo
struct	Arco

Macros
#define	INDENT   " "

Typedefs
typedef Graph_Node< Nodo >	Node_Nodo
typedef Graph_Arc< Arco >	Arco_Arco
typedef List_Digraph< Node_Nodo, Arco_Arco >	Grafo

Functions
void	insertar_arco (Grafo &grafo, const string &src_name, const string &tgt_name, const double &distancia)
void	build_test_graph (Grafo &g)
void	copia_Arco_Arco (Arco_Arco *arc, const long &, const long &, double &value)
int	main ()

Variables
const Arco	Arco_Zero (0)

Detailed Description

Floyd-Warshall algorithm with LaTeX output generation.

This example demonstrates the Floyd-Warshall algorithm for finding shortest paths between all pairs of vertices in a weighted graph. It generates step-by-step LaTeX matrices showing the algorithm's progression, making it ideal for educational purposes and algorithm visualization.

What is Floyd-Warshall?

Problem

All-pairs shortest paths: Find shortest paths between every pair of vertices in a weighted graph.

Solution: Floyd-Warshall Algorithm

Floyd-Warshall is a dynamic programming algorithm that finds shortest paths between all pairs of vertices in a single run. Unlike Dijkstra (single-source) or Johnson (all-pairs using Dijkstra), Floyd-Warshall works directly with the adjacency matrix.

Key Characteristics

• All-pairs: Finds all shortest paths in one algorithm run
• Matrix-based: Works with adjacency/distance matrix
• Dynamic programming: Builds solution incrementally
• Negative weights: Handles negative edges (but not negative cycles)

Algorithm Overview

Dynamic Programming Recurrence

The algorithm uses dynamic programming with the recurrence:

D^(k)[i][j] = min(D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j])

Where:

• D^(k)[i][j]: Shortest path from i to j using only vertices {1..k}
• D^(0)[i][j]: Direct edge weight (or ∞ if no edge)
• D^(V)[i][j]: Final shortest path distance

Key Insight

At iteration k, we consider whether going through vertex k gives a shorter path than the current best path:

• Option 1: Current best path D^(k-1)[i][j]
• Option 2: Path through k: D^(k-1)[i][k] + D^(k-1)[k][j]
• Choose: Minimum of the two

Algorithm Pseudocode

Floyd-Warshall(G):
  // Initialize distance matrix
  for each vertex i:
    for each vertex j:
      D[i][j] = weight(i,j) if edge exists, else ∞
  
  // Main algorithm
  for k = 1 to V:
    for i = 1 to V:
      for j = 1 to V:
        D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Complexity

Time Complexity

• O(V³): Three nested loops over vertices
• Independent of edges: Same for sparse and dense graphs
• Cubic: Can be slow for large graphs

Space Complexity

• O(V²): Distance matrix
• Can optimize: Use single matrix (in-place updates)

Comparison

Algorithm	Time	Space	Best For
Floyd-Warshall	O(V³)	O(V²)	Dense graphs
Johnson	O(V² log V + VE)	O(V²)	Sparse graphs
V × Dijkstra	O(V(V log V + E))	O(V²)	Non-negative only

Advantages

• All-pairs: Finds all shortest paths in one run
• Negative weights: Handles negative edge weights
• Simple: Easy to implement and understand
• Path reconstruction: Can reconstruct actual paths
• Transitive closure: Can find reachability (set weights to 1)

Limitations

• No negative cycles: Algorithm fails if graph has negative cycles
• Cubic time: Slower than Johnson for sparse graphs
• Dense graphs: Best suited for dense graphs (many edges)
• Memory: O(V²) space requirement

Applications

Network Routing

• Communication networks: Find shortest paths between routers
• Internet routing: All-pairs routing tables
• Network analysis: Understand network topology

Graph Analysis

• Graph diameter: Longest shortest path
• Eccentricity: Maximum distance from vertex
• Centrality: Betweenness, closeness centrality

Transitive Closure

• Reachability: Determine if paths exist (set weights to 1)
• Connectivity: Find strongly connected components
• Dependency analysis: Analyze dependencies

Social Networks

• Shortest paths: Find shortest connection paths
• Degrees of separation: Measure social distance
• Network metrics: Analyze network structure

Transportation

• All-pairs routes: Find shortest routes between all cities
• Route planning: Plan routes efficiently
• Logistics: Optimize transportation networks

Output Files

LaTeX Matrices

Generates mat-floyd.tex containing:

• D^(0): Initial distance matrix (direct edges only)
• D^(k): Distance matrices after each intermediate vertex k
• Path matrix: For reconstructing actual paths
• Formatted: All as LaTeX tables ready for compilation

Educational Value

The LaTeX output shows:

• Step-by-step: How distances update at each iteration
• Visualization: Easy to see algorithm progression
• Documentation: Can be included in papers/presentations

Test Graph

Graph Structure

Uses a predefined 9-node directed graph (labeled A through I) with:

• Weighted edges: Some positive, some negative
• No negative cycles: Algorithm works correctly
• Mixed weights: Demonstrates algorithm behavior

Graph Properties

• Directed: Edges have direction
• Weighted: Edges have weights (can be negative)
• No negative cycles: Assumed (otherwise shortest paths are undefined)

Usage

# Generate LaTeX output
./write_floyd
 
# Compile LaTeX to PDF
pdflatex mat-floyd.tex
 
# View results
evince mat-floyd.pdf  # or your PDF viewer

Path Reconstruction

How to Reconstruct Paths

The algorithm maintains a next-hop matrix P:

• P[i][j] stores the next vertex index to move to when going from i to j along a shortest path.

A simple reconstruction procedure is:

reconstruct_path(i, j):
  if D[i][j] == ∞:
    return []
  path = [i]
  while i != j:
    i = P[i][j]
    path.append(i)
  return path

Time: O(path_length) to reconstruct one path

Negative Cycle Detection

How to Detect Negative Cycles

In general, a negative cycle implies that at least one diagonal entry becomes negative (some D[i][i] < 0) after relaxation.

Note: this example generates the LaTeX trace but does not perform an explicit negative-cycle check.

See also

johnson_example.cc Johnson's algorithm (better for sparse graphs)

dijkstra_example.cc Dijkstra's algorithm (single-source)

Author

Leandro Rabindranath León

Definition in file write_floyd.C.

Macro Definition Documentation

INDENT

#define INDENT   " "

Definition at line 259 of file write_floyd.C.

Typedef Documentation

Arco_Arco

typedef Graph_Arc<Arco> Arco_Arco

Definition at line 350 of file write_floyd.C.

Grafo

typedef List_Digraph<Node_Nodo, Arco_Arco> Grafo

Definition at line 352 of file write_floyd.C.

Node_Nodo

typedef Graph_Node<Nodo> Node_Nodo

Definition at line 348 of file write_floyd.C.

Function Documentation

build_test_graph()

void build_test_graph

(

Grafo &

g

)

Definition at line 375 of file write_floyd.C.

References insertar_arco().

Referenced by main().

copia_Arco_Arco()

void copia_Arco_Arco	(	Arco_Arco *	arc,
		const long &	,
		const long &	,
		double &	value
	)

Definition at line 410 of file write_floyd.C.

References GTArcCommon< ArcInfo >::get_info().

insertar_arco()

void insertar_arco	(	Grafo &	grafo,
		const string &	src_name,
		const string &	tgt_name,
		const double &	distancia
	)

Definition at line 355 of file write_floyd.C.

References Aleph::maps().

Referenced by build_test_graph().

main()

int main

(

)

Definition at line 416 of file write_floyd.C.

References build_test_graph(), and Aleph::maps().

Variable Documentation

Arco_Zero

const Arco Arco_Zero(0)

(

0

)