Shortest Paths DP

def bellman_ford(graph, start):
    """
    Bellman-Ford algorithm.
    graph: [(u, v, weight), ...]
    Time: O(V * E), Space: O(V)
    """
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    
    # Relax edges V-1 times
    for _ in range(n - 1):
        for u, v, weight in graph:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    # Check for negative cycles
    for u, v, weight in graph:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return None, True  # Negative cycle detected
    
    return dist, False

def floyd_warshall(graph):
    """
    All pairs shortest paths.
    graph: adjacency matrix
    Time: O(V³), Space: O(V²)
    """
    n = len(graph)
    dist = [row[:] for row in graph]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist