Class BellmanFordUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.BellmanFordUtil
public final class BellmanFordUtil extends Object
Bellman-Ford Util - Single-source shortest paths with negative weight support Bellman-Ford工具类 - 支持负权重的单源最短路径

Implements the Bellman-Ford algorithm for computing single-source shortest paths in graphs that may contain negative weight edges. Detects negative cycles.

实现Bellman-Ford算法，用于计算可能包含负权重边的图中的单源最短路径。可检测负环。

Features | 主要功能:

  • Single-source shortest paths with negative weights - 支持负权重的单源最短路径
  • Negative cycle detection - 负环检测
  • Negative cycle extraction - 负环提取
  • Path reconstruction between two vertices - 两顶点间路径重建

Usage Examples | 使用示例:

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

Map<String, Double> distances = BellmanFordUtil.shortestPaths(graph, "A");
List<String> path = BellmanFordUtil.shortestPath(graph, "A", "C");
boolean hasNeg = BellmanFordUtil.hasNegativeCycle(graph, "A");

Security | 安全性:

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

Performance | 性能特性:

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

  • Method Details

    • shortestPaths

      public static <V> Map<V,Double> shortestPaths(Graph<V> graph, V source)
      Compute single-source shortest paths using Bellman-Ford algorithm. Supports negative edge weights. Throws if a negative cycle is reachable from source. 使用Bellman-Ford算法计算单源最短路径。支持负权重边。如果从源可达负环则抛出异常。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      Returns:
      map of vertex to shortest distance from source | 从源顶点到各顶点的最短距离映射
      Throws:
      InvalidVertexException - if source is null | 当源顶点为null时抛出
      GraphException - with NEGATIVE_CYCLE if a negative cycle is reachable from source | 当从源可达负环时抛出NEGATIVE_CYCLE

    • shortestPath

      public static <V> List<V> shortestPath(Graph<V> graph, V source, V target)
      Find shortest path between two vertices using Bellman-Ford algorithm. 使用Bellman-Ford算法查找两顶点间的最短路径。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      target - the target vertex | 目标顶点
      Returns:
      list of vertices in the shortest path, or empty list if no path | 最短路径的顶点列表，无路径时返回空列表
      Throws:
      InvalidVertexException - if source or target is null | 当源或目标顶点为null时抛出
      GraphException - with NEGATIVE_CYCLE if a negative cycle is reachable from source | 当从源可达负环时抛出NEGATIVE_CYCLE

    • hasNegativeCycle

      public static <V> boolean hasNegativeCycle(Graph<V> graph, V source)
      Check if a negative cycle is reachable from the given source vertex. 检查从给定源顶点是否可达负环。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      Returns:
      true if a negative cycle is reachable from source | 如果从源可达负环返回true
      Throws:
      InvalidVertexException - if source is null | 当源顶点为null时抛出

    • findNegativeCycle

      public static <V> List<V> findNegativeCycle(Graph<V> graph, V source)
      Find and return a negative cycle reachable from the given source vertex. 查找并返回从给定源顶点可达的负环。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      Returns:
      list of vertices forming a negative cycle, or empty list if no negative cycle | 形成负环的顶点列表，无负环时返回空列表
      Throws:
      InvalidVertexException - if source is null | 当源顶点为null时抛出