execute method

  1. @override
BellmanFordResult<T> execute(
  1. BellmanFordInput<T> input
)
override

Execute the algorithm on the given input.

This method should be:

  • Fast: optimized for the hot path with minimal allocations
  • Pure: no side effects (unless documented otherwise)
  • Predictable: consistent behavior for the same input

Preconditions:

  • canApply(input, hint) must return true
  • Input must meet the strategy's requirements (e.g., sorted if requiresSorted)

The caller is responsible for ensuring preconditions are met.

Implementation

@override
BellmanFordResult<T> execute(BellmanFordInput<T> input) {
  final graph = input.graph;
  final source = input.source;

  if (!graph.hasVertex(source)) {
    throw ArgumentError('Source vertex $source not found in graph');
  }

  final vertices = graph.vertices;
  final distances = <T, double>{};
  final predecessors = <T, T?>{};

  // Initialize distances
  for (final vertex in vertices) {
    distances[vertex] = vertex == source ? 0.0 : double.infinity;
    predecessors[vertex] = null;
  }

  // Relax edges repeatedly
  for (int i = 0; i < vertices.length - 1; i++) {
    for (final vertex in vertices) {
      if (distances[vertex] != double.infinity) {
        for (final edge in graph.getEdges(vertex)) {
          final neighbor = edge.destination;
          final weight = edge.weight;
          final newDistance = distances[vertex]! + weight;

          if (newDistance < distances[neighbor]!) {
            distances[neighbor] = newDistance;
            predecessors[neighbor] = vertex;
          }
        }
      }
    }
  }

  // Check for negative cycles
  bool hasNegativeCycle = false;
  for (final vertex in vertices) {
    if (distances[vertex] != double.infinity) {
      for (final edge in graph.getEdges(vertex)) {
        final neighbor = edge.destination;
        final weight = edge.weight;
        final newDistance = distances[vertex]! + weight;

        if (newDistance < distances[neighbor]!) {
          hasNegativeCycle = true;
          break;
        }
      }
      if (hasNegativeCycle) break;
    }
  }

  return BellmanFordResult(
    ShortestPathResult(distances, predecessors, source),
    hasNegativeCycle,
  );
}