Class FloydWarshallUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.FloydWarshallUtil
public final class FloydWarshallUtil extends Object
Floyd-Warshall Util - All-pairs shortest paths Floyd-Warshall工具类 - 全源最短路径

Implements the Floyd-Warshall algorithm for computing all-pairs shortest paths. Supports negative edge weights and detects negative cycles.

实现Floyd-Warshall算法，计算全源最短路径。支持负权重边并检测负环。

Features | 主要功能:

  • All-pairs shortest paths - 全源最短路径
  • Path reconstruction - 路径重建
  • Negative cycle detection - 负环检测
  • Distance matrix - 距离矩阵

Usage Examples | 使用示例:

Graph<String> graph = new DirectedGraph<>();
graph.addEdge("A", "B", 3.0);
graph.addEdge("B", "C", 2.0);

FloydWarshallUtil.AllPairsResult<String> result = FloydWarshallUtil.compute(graph);
double dist = result.distance("A", "C");
List<String> path = result.path("A", "C");

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns empty result for null graph) - 空值安全: 是

Performance | 性能特性:

  • Time complexity: O(V^3) - 时间复杂度: O(V^3)
  • Space complexity: O(V^2) - 空间复杂度: O(V^2)
Since:
JDK 25, opencode-base-graph V1.0.3
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • compute

      public static <V> FloydWarshallUtil.AllPairsResult<V> compute(Graph<V> graph)
      Compute all-pairs shortest paths using Floyd-Warshall algorithm. 使用Floyd-Warshall算法计算全源最短路径。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      all-pairs shortest path result | 全源最短路径结果
      Throws:
      GraphException - with LIMIT_EXCEEDED if graph has more than 1000 vertices | 当图的顶点数超过1000时抛出LIMIT_EXCEEDED