Floyd-Warshall Algorithm

The Floyd-Warshall algorithm finds shortest paths between all pairs of vertices in a weighted graph, handling both positive and negative edge weights (but not negative cycles).

Algorithm Overview

Floyd-Warshall uses dynamic programming to compute shortest paths between all vertex pairs. It considers each vertex as an intermediate point and updates distances when a shorter path is found through that vertex.

Key Features

All-Pairs: Finds shortest paths between every pair of vertices
Negative Weights: Handles negative edge weights (unlike Dijkstra)
Cycle Detection: Can detect negative cycles in the graph
Dense Graphs: Efficient for small to medium dense graphs

Available Functions

Basic Floyd-Warshall

floyd_warshall(graph) -> Dict[Tuple[Any, Any], float]

Returns shortest distances between all pairs of vertices.

Path Reconstruction

get_shortest_path(graph, start, end) -> Optional[Tuple[float, List[Any]]]

Returns shortest distance and path between two specific vertices.

Negative Cycle Detection

has_negative_cycle(graph) -> bool

Checks if the graph contains any negative cycles.

Usage Examples

Basic All-Pairs Shortest Paths

from algo.data_structs.graphs import AdjacencyListGraph
from algo.algorithms.graphs import floyd_warshall

# Create a delivery network with costs
delivery = AdjacencyListGraph(directed=True)

# Add routes with delivery costs
routes = [
    ('Warehouse', 'Store_A', 10),
    ('Warehouse', 'Store_B', 15),
    ('Store_A', 'Store_B', 8),
    ('Store_A', 'Store_C', 12),
    ('Store_B', 'Store_C', 6),
    ('Store_C', 'Customer', 5),
    ('Store_B', 'Customer', 20),
]

for from_loc, to_loc, cost in routes:
    delivery.add_edge(from_loc, to_loc, cost)

# Find all shortest delivery costs
all_distances = floyd_warshall(delivery)

# Display delivery costs matrix
locations = list(delivery.get_vertices())
print("Delivery Cost Matrix:")
print(f"{'From/To':<12}", end="")
for to_loc in locations:
    print(f"{to_loc:<12}", end="")
print()

for from_loc in locations:
    print(f"{from_loc:<12}", end="")
    for to_loc in locations:
        cost = all_distances[(from_loc, to_loc)]
        if cost == float('inf'):
            print(f"{'∞':<12}", end="")
        else:
            print(f"{cost:<12}", end="")
    print()

Path Reconstruction with Analysis

from algo.algorithms.graphs import get_shortest_path

# Find specific delivery route
result = get_shortest_path(delivery, 'Warehouse', 'Customer')

if result:
    cost, path = result
    print(f"\nOptimal delivery route:")
    print(f"Path: {' -> '.join(path)}")
    print(f"Total cost: ${cost}")

    # Analyze route segments
    print(f"\nRoute breakdown:")
    for i in range(len(path) - 1):
        from_loc = path[i]
        to_loc = path[i + 1]
        segment_cost = delivery.get_edge_weight(from_loc, to_loc)
        print(f"  {from_loc} to {to_loc}: ${segment_cost}")

# Compare all possible routes to customer
print(f"\nAll routes to Customer:")
for location in locations:
    if location != 'Customer':
        distance = all_distances[(location, 'Customer')]
        if distance != float('inf'):
            print(f"  From {location}: ${distance}")

Negative Weight Handling

# Model a financial arbitrage scenario
finance = AdjacencyListGraph(directed=True)

# Currency exchange rates (negative log for arbitrage detection)
# Positive weights = cost, negative weights = profit
exchanges = [
    ('USD', 'EUR', 0.1),    # Small exchange fee
    ('EUR', 'GBP', 0.05),   # Small exchange fee
    ('GBP', 'USD', -0.2),   # Profitable exchange rate
    ('USD', 'JPY', 0.08),
    ('JPY', 'EUR', -0.05),  # Profitable exchange
]

for from_curr, to_curr, rate in exchanges:
    finance.add_edge(from_curr, to_curr, rate)

# Check for arbitrage opportunities (negative cycles)
from algo.algorithms.graphs import has_negative_cycle

if has_negative_cycle(finance):
    print("Arbitrage opportunity detected!")

    # Find the cycle (simplified approach)
    all_paths = floyd_warshall(finance)
    for currency in finance.get_vertices():
        self_cost = all_paths[(currency, currency)]
        if self_cost < 0:
            print(f"Profitable cycle starting from {currency}: {self_cost}")
else:
    print("No arbitrage opportunities found.")

Network Analysis and Optimization

# Analyze network efficiency
def analyze_network_diameter(graph):
    """Find the network diameter and analyze connectivity."""
    distances = floyd_warshall(graph)
    vertices = list(graph.get_vertices())

    max_distance = 0
    total_distance = 0
    reachable_pairs = 0
    unreachable_pairs = []

    for from_v in vertices:
        for to_v in vertices:
            if from_v != to_v:
                dist = distances[(from_v, to_v)]
                if dist != float('inf'):
                    max_distance = max(max_distance, dist)
                    total_distance += dist
                    reachable_pairs += 1
                else:
                    unreachable_pairs.append((from_v, to_v))

    avg_distance = total_distance / reachable_pairs if reachable_pairs > 0 else 0
    total_pairs = len(vertices) * (len(vertices) - 1)
    connectivity = reachable_pairs / total_pairs if total_pairs > 0 else 0

    return {
        'diameter': max_distance,
        'average_distance': avg_distance,
        'connectivity': connectivity,
        'unreachable_pairs': unreachable_pairs
    }

# Analyze the delivery network
analysis = analyze_network_diameter(delivery)
print(f"\nNetwork Analysis:")
print(f"  Network diameter: {analysis['diameter']}")
print(f"  Average distance: {analysis['average_distance']:.2f}")
print(f"  Connectivity: {analysis['connectivity']:.1%}")

if analysis['unreachable_pairs']:
    print(f"  Unreachable routes:")
    for from_loc, to_loc in analysis['unreachable_pairs'][:5]:  # Show first 5
        print(f"    {from_loc} -> {to_loc}")

Comparison with Dijkstra

# Compare Floyd-Warshall vs multiple Dijkstra runs
from algo.algorithms.graphs import dijkstra
import time

# Create a medium-sized graph
test_graph = AdjacencyListGraph(directed=True)
vertices = [f"V{i}" for i in range(20)]

# Add random edges
import random
random.seed(42)
for _ in range(60):
    from_v = random.choice(vertices)
    to_v = random.choice(vertices)
    if from_v != to_v:
        weight = random.randint(1, 10)
        test_graph.add_edge(from_v, to_v, weight)

# Time Floyd-Warshall
start_time = time.time()
floyd_result = floyd_warshall(test_graph)
floyd_time = time.time() - start_time

# Time multiple Dijkstra runs
start_time = time.time()
dijkstra_results = {}
for vertex in vertices:
    distances = dijkstra(test_graph, vertex)
    for target, dist in distances.items():
        dijkstra_results[(vertex, target)] = dist
dijkstra_time = time.time() - start_time

print(f"\nPerformance Comparison:")
print(f"  Floyd-Warshall: {floyd_time:.4f} seconds")
print(f"  Multiple Dijkstra: {dijkstra_time:.4f} seconds")
print(f"  Ratio: {dijkstra_time / floyd_time:.2f}x")

# Verify results are equivalent
mismatches = 0
for key in floyd_result:
    if abs(floyd_result[key] - dijkstra_results[key]) > 1e-10:
        mismatches += 1

print(f"  Result verification: {'✓ Identical' if mismatches == 0 else f'✗ {mismatches} mismatches'}")

Real-World Applications

# Model influence propagation in social network
social = AdjacencyListGraph(directed=True)

# Add influence relationships (lower = stronger influence)
influences = [
    ('Alice', 'Bob', 2),      # Alice influences Bob moderately
    ('Alice', 'Carol', 1),    # Alice strongly influences Carol
    ('Bob', 'David', 3),      # Bob weakly influences David
    ('Carol', 'David', 1),    # Carol strongly influences David
    ('David', 'Eve', 2),      # David moderately influences Eve
    ('Carol', 'Eve', 4),      # Carol weakly influences Eve
]

for person1, person2, strength in influences:
    social.add_edge(person1, person2, strength)

# Find influence paths
influence_paths = floyd_warshall(social)

print("Social Influence Analysis:")
people = list(social.get_vertices())
for influencer in people:
    print(f"\n{influencer}'s influence reach:")
    for target in people:
        if influencer != target:
            influence = influence_paths[(influencer, target)]
            if influence != float('inf'):
                path_result = get_shortest_path(social, influencer, target)
                if path_result:
                    _, path = path_result
                    print(f"  -> {target}: strength {influence} via {' -> '.join(path)}")

Supply Chain Optimization

# Model supply chain with lead times
supply_chain = AdjacencyListGraph(directed=True)

# Add supply relationships with lead times (days)
supply_links = [
    ('Supplier_A', 'Factory_1', 3),
    ('Supplier_B', 'Factory_1', 5),
    ('Supplier_A', 'Factory_2', 4),
    ('Factory_1', 'Warehouse', 2),
    ('Factory_2', 'Warehouse', 3),
    ('Warehouse', 'Store_1', 1),
    ('Warehouse', 'Store_2', 2),
    ('Factory_1', 'Store_1', 4),  # Direct shipping option
]

for from_node, to_node, days in supply_links:
    supply_chain.add_edge(from_node, to_node, days)

# Analyze supply chain efficiency
supply_times = floyd_warshall(supply_chain)

print("Supply Chain Lead Times:")
suppliers = ['Supplier_A', 'Supplier_B']
stores = ['Store_1', 'Store_2']

for supplier in suppliers:
    for store in stores:
        lead_time = supply_times[(supplier, store)]
        if lead_time != float('inf'):
            path_info = get_shortest_path(supply_chain, supplier, store)
            if path_info:
                _, path = path_info
                print(f"{supplier} -> {store}: {lead_time} days via {' -> '.join(path)}")

Performance Characteristics

Time Complexity

All Cases: O(V³) - three nested loops over all vertices
Independent of Edges: Performance depends only on vertex count

Space Complexity

Distance Matrix: O(V²) for storing all pairwise distances
Path Reconstruction: Additional O(V²) for predecessor matrix

Graph Size Guidelines

Vertices	Approximate Runtime	Memory Usage
100	< 1 second	~80 KB
500	~1 second	~2 MB
1000	~8 seconds	~8 MB
2000	~1 minute	~32 MB

Algorithm Comparison

Floyd-Warshall vs Dijkstra

Aspect	Floyd-Warshall	Multiple Dijkstra
Time Complexity	O(V³)	O(V × (V + E) log V)
Space Complexity	O(V²)	O(V²) for all results
Negative Weights	✓ Supported	✗ Not supported
Negative Cycles	✓ Detectable	✗ Not detectable
Best For	Small dense graphs	Large sparse graphs
All-pairs queries	✓ Optimal	✗ Suboptimal

When to Use Floyd-Warshall

Choose Floyd-Warshall when:

Need all-pairs shortest paths
Graph has negative edge weights
Graph is small to medium-sized (< 1000 vertices)
Need to detect negative cycles
Graph is dense (many edges)

Choose Dijkstra when:

Need single-source shortest paths
Only positive edge weights
Graph is large (> 1000 vertices)
Graph is sparse (few edges)
Memory usage is critical

Best Practices

Size Limitations: Be cautious with graphs > 1000 vertices due to O(V³) complexity
Memory Management: Floyd-Warshall uses O(V²) memory regardless of edge count
Negative Cycle Handling: Always check for negative cycles when dealing with negative weights
Path Reconstruction: Use get_shortest_path() for individual paths rather than storing all paths
Alternative Algorithms: Consider Johnson's algorithm for sparse graphs with negative weights

API Reference

Floyd-Warshall algorithm for finding shortest paths between all pairs of vertices.

This module provides an implementation of the Floyd-Warshall algorithm that works with any graph implementation following the Graph interface.

`floyd_warshall(graph)`

Find shortest paths between all pairs of vertices using Floyd-Warshall algorithm.

Parameters:

Name	Type	Description	Default
`graph`	`Graph`	A graph implementation following the Graph interface	required

Returns:

Type	Description
`Dict[Tuple[Any, Any], float]`	A dictionary mapping (from_vertex, to_vertex) tuples to shortest path distances

Time Complexity: O(V³) where V is the number of vertices Space Complexity: O(V²)

`get_shortest_path(graph, start, end)`

Get the shortest path between two vertices using Floyd-Warshall with path reconstruction.

Parameters:

Name	Type	Description	Default
`graph`	`Graph`	A graph implementation following the Graph interface	required
`start`	`Any`	Starting vertex	required
`end`	`Any`	Ending vertex	required

Returns:

Type	Description
`Optional[Tuple[float, list]]`	A tuple of (distance, path) if path exists, None otherwise
`Optional[Tuple[float, list]]`	The path is a list of vertices from start to end

`has_negative_cycle(graph)`

Check if the graph has a negative cycle using Floyd-Warshall.

Parameters:

Name	Type	Description	Default
`graph`	`Graph`	A graph implementation following the Graph interface	required

Returns:

Type	Description
`bool`	True if the graph contains a negative cycle, False otherwise

Floyd-Warshall Algorithm

Algorithm Overview

Key Features

Available Functions

Basic Floyd-Warshall

Path Reconstruction

Negative Cycle Detection

Usage Examples

Basic All-Pairs Shortest Paths

Path Reconstruction with Analysis

Negative Weight Handling

Network Analysis and Optimization

Comparison with Dijkstra

Real-World Applications

Social Network Analysis

Supply Chain Optimization

Performance Characteristics

Time Complexity

Space Complexity

Graph Size Guidelines

Algorithm Comparison

Floyd-Warshall vs Dijkstra

When to Use Floyd-Warshall

Best Practices

API Reference

floyd_warshall(graph)

get_shortest_path(graph, start, end)

has_negative_cycle(graph)

`floyd_warshall(graph)`

`get_shortest_path(graph, start, end)`

`has_negative_cycle(graph)`