Class BellmanFordShortestPath<V,W>

java.lang.Object
org.episteme.core.mathematics.discrete.BellmanFordShortestPath<V,W>
public class BellmanFordShortestPath<V,W> extends Object
Bellman-Ford algorithm for single-source shortest paths.

Unlike Dijkstra's algorithm, Bellman-Ford can handle negative edge weights and detects negative cycles. Time complexity is O(VE).

*

Reference:
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16, 87-90.

Since:
1.0
Author:
Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

  • Constructor Details

    • BellmanFordShortestPath

      public BellmanFordShortestPath(GraphWeightAdapter<W> weightAdapter)

  • Method Details

    • ofDouble

      public static <V> BellmanFordShortestPath<V,Double> ofDouble()
      Creates an instance for Double weights.

    • ofReal

      public static <V> BellmanFordShortestPath<V,Real> ofReal()
      Creates an instance for Real weights.

    • findPath

      public ShortestPathResult<V,W> findPath(WeightedGraph<V,W> graph, V source, V target)
      Computes shortest path from source to target.
      Parameters:
      graph - the graph
      source - source vertex
      target - target vertex
      Returns:
      result containing distance and path, or negative cycle detection

    • findAllPaths

      public Optional<Map<V,W>> findAllPaths(WeightedGraph<V,W> graph, V source)
      Computes shortest paths from source to all vertices.
      Parameters:
      graph - the graph
      source - source vertex
      Returns:
      map of distances from source, or empty if negative cycle detected