Class FloydWarshallShortestPath<V,W>

java.lang.Object

org.episteme.core.mathematics.discrete.FloydWarshallShortestPath<V,W>

public class FloydWarshallShortestPath<V,W>
extends Object

Floyd-Warshall algorithm for all-pairs shortest paths.

Computes shortest paths between all pairs of vertices in O(V³) time. Can handle negative weights but will detect negative cycles.

*

Reference:
Floyd, R. W. (1962). Algorithm 97: Shortest Path. Communications of the ACM, 5(6), 345.

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Constructor Summary

Constructors

Constructor	Description
FloydWarshallShortestPath(GraphWeightAdapter<W> weightAdapter)

Method Summary

Modifier and Type	Method	Description
Optional<Map<V,Map<V,W>>>	findAllPaths(WeightedGraph<V,W> graph)	Computes all-pairs shortest paths.
static <V> FloydWarshallShortestPath<V,Double>	ofDouble()
static <V> FloydWarshallShortestPath<V,Real>	ofReal()

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

FloydWarshallShortestPath

public FloydWarshallShortestPath(GraphWeightAdapter<W> weightAdapter)

Method Details

ofDouble

public static <V>
FloydWarshallShortestPath<V,Double> ofDouble()

ofReal

public static <V> FloydWarshallShortestPath<V,Real> ofReal()

findAllPaths

public Optional<Map<V,Map<V,W>>> findAllPaths(WeightedGraph<V,W> graph)

Computes all-pairs shortest paths.

Parameters:

graph - the graph

Returns:

map of (source, target) pairs to distances, or empty if negative cycle