Skip to content

Graph Algorithms Overview

This section contains documentation for graph algorithms that work with the Graph interface.

Available Graph Algorithms

Shortest Path Algorithms

  • Dijkstra's Algorithm: Single-source shortest paths for non-negative weights
  • Floyd-Warshall Algorithm: All-pairs shortest paths with cycle detection

Algorithm Compatibility

All graph algorithms in this library are designed to work with any implementation of the Graph interface:

  • AdjacencyListGraph
  • AdjacencyMatrixGraph
  • Custom graph implementations

This design ensures that you can: - Switch between graph representations without changing algorithm code - Test algorithms with different graph implementations - Optimize for different use cases (sparse vs dense graphs)

Performance Considerations

Choose Algorithms Based on Graph Properties

Graph Property Recommended Algorithm
Non-negative weights Dijkstra's Algorithm
Negative weights allowed Floyd-Warshall Algorithm
Single source/destination Dijkstra's Algorithm
All-pairs shortest paths Floyd-Warshall Algorithm
Large sparse graphs Dijkstra's Algorithm
Small dense graphs Floyd-Warshall Algorithm

Graph Representation Impact

Algorithm Adjacency List Adjacency Matrix
Dijkstra O((V + E) log V) O(V² log V)
Floyd-Warshall O(V³) O(V³)

Common Usage Patterns

Single Shortest Path

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

# Create graph
graph = AdjacencyListGraph(directed=True)
graph.add_edge('A', 'B', 4)
graph.add_edge('B', 'C', 2)
graph.add_edge('A', 'C', 10)

# Find shortest path
result = dijkstra_with_path(graph, 'A', 'C')
if result:
    distance, path = result
    print(f"Shortest path from A to C: {' -> '.join(path)} (distance: {distance})")

All Shortest Paths

from algo.algorithms.graphs import floyd_warshall

# Find all shortest paths
all_paths = floyd_warshall(graph)

# Access any path
distance_a_to_c = all_paths[('A', 'C')]
print(f"Distance from A to C: {distance_a_to_c}")

Multiple Destinations

from algo.algorithms.graphs import dijkstra_all_paths

# Find paths to all reachable vertices
all_destinations = dijkstra_all_paths(graph, 'A')

for vertex, (distance, path) in all_destinations.items():
    print(f"Path to {vertex}: {' -> '.join(path)} (distance: {distance})")

Algorithm Selection Guide

Use Dijkstra When:

  • Finding shortest path from one source to one or more destinations
  • Graph has non-negative edge weights
  • Working with large, sparse graphs
  • Need optimal performance for single-source queries

Use Floyd-Warshall When:

  • Finding shortest paths between all pairs of vertices
  • Graph may have negative edge weights (but no negative cycles)
  • Working with small to medium graphs
  • Need to detect negative cycles
  • Precomputing all distances for multiple queries

Error Handling

All graph algorithms handle common edge cases:

# Non-existent vertices
result = dijkstra_with_path(graph, 'X', 'Y')  # Returns None

# Unreachable destinations  
distances = dijkstra(graph, 'A')
print(distances['isolated_vertex'])  # float('inf')

# Negative cycles
has_negative = has_negative_cycle(graph)  # Boolean result

Integration Examples

With Different Graph Types

# Same algorithm, different representations
from algo.data_structs.graphs import AdjacencyListGraph, AdjacencyMatrixGraph

list_graph = AdjacencyListGraph()
matrix_graph = AdjacencyMatrixGraph(max_vertices=100)

# Build same graph structure
edges = [('A', 'B', 1), ('B', 'C', 2), ('A', 'C', 5)]
for from_v, to_v, weight in edges:
    list_graph.add_edge(from_v, to_v, weight)
    matrix_graph.add_edge(from_v, to_v, weight)

# Same algorithm works with both
list_result = dijkstra(list_graph, 'A')
matrix_result = dijkstra(matrix_graph, 'A')

assert list_result == matrix_result  # Same results

Custom Graph Analysis

def analyze_connectivity(graph, algorithms=['dijkstra', 'floyd_warshall']):
    """Comprehensive graph connectivity analysis."""
    results = {}

    if 'dijkstra' in algorithms:
        # Check reachability from each vertex
        vertices = list(graph.get_vertices())
        for start in vertices:
            distances = dijkstra(graph, start)
            reachable = sum(1 for d in distances.values() if d != float('inf'))
            results[f'reachable_from_{start}'] = reachable

    if 'floyd_warshall' in algorithms:
        # Check overall connectivity
        all_paths = floyd_warshall(graph)
        total_pairs = len(graph.get_vertices()) ** 2
        connected_pairs = sum(1 for d in all_paths.values() if d != float('inf'))
        results['connectivity_ratio'] = connected_pairs / total_pairs

    return results

# Use with any graph implementation
connectivity = analyze_connectivity(graph)
print(f"Graph connectivity analysis: {connectivity}")