Class AStarUtil

java.lang.Object

cloud.opencode.base.graph.algorithm.AStarUtil

public final class AStarUtil
extends Object

A* Algorithm Util A*算法工具类

A* pathfinding algorithm with heuristic function support.

支持启发式函数的A*寻路算法。

Features | 特性:

• Heuristic-guided search | 启发式引导搜索
• Optimal path finding | 最优路径查找
• Faster than Dijkstra with good heuristic | 使用好的启发式函数比Dijkstra更快

Time Complexity | 时间复杂度: O(E) ~ O(V²) depending on heuristic

Usage Examples | 使用示例:

// With custom heuristic
BiFunction<String, String, Double> heuristic = (a, b) ->
    Math.abs(a.hashCode() - b.hashCode());
List<String> path = AStarUtil.findPath(graph, "A", "Z", heuristic);

// With zero heuristic (equivalent to Dijkstra)
List<String> path = AStarUtil.findPath(graph, "A", "Z", (a, b) -> 0.0);

Security | 安全性:

• Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
• Null-safe: Yes (returns empty results for null inputs) - 空值安全: 是（null输入返回空结果）

Performance | 性能特性:

• Time complexity: O(E log V) with good heuristic - 时间复杂度: O(E log V)（启发式函数较好时）
• Space complexity: O(V) - 空间复杂度: O(V)

Since:

JDK 25, opencode-base-graph V1.0.0

Author:

Leon Soo www.LeonSoo.com

See Also:

• OpenCode.cloud

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	AStarUtil.PathResult<V>	Result of A* search including path and cost A*搜索结果，包含路径和成本

Method Summary

Modifier and Type	Method	Description
static <V> List<V>	findPath(Graph<V> graph, V source, V target)	Find path with zero heuristic (equivalent to Dijkstra) 使用零启发式函数查找路径（等同于Dijkstra）
static <V> List<V>	findPath(Graph<V> graph, V source, V target, BiFunction<V,V,Double> heuristic)	Find shortest path using A* algorithm 使用A*算法查找最短路径
static <V> AStarUtil.PathResult<V>	findPathDetailed(Graph<V> graph, V source, V target, BiFunction<V,V,Double> heuristic)	Find path with detailed result 查找路径并返回详细结果
static <V> List<V>	findPathWithCostLimit(Graph<V> graph, V source, V target, BiFunction<V,V,Double> heuristic, double maxCost)	Find path with cost limit 使用成本限制查找路径

Methods inherited from class Object

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

Method Details

findPath

public static <V> List<V> findPath(Graph<V> graph,
 V source,
 V target,
 BiFunction<V,V,Double> heuristic)

Find shortest path using A* algorithm 使用A*算法查找最短路径

Type Parameters:

V - the vertex type | 顶点类型

Parameters:

graph - the graph | 图

source - the source vertex | 源顶点

target - the target vertex | 目标顶点

heuristic - the heuristic function h(n) estimating distance to target | 启发式函数h(n)估计到目标的距离

Returns:

list of vertices in the shortest path, or empty list if no path | 最短路径的顶点列表，无路径时返回空列表

findPath

public static <V> List<V> findPath(Graph<V> graph,
 V source,
 V target)

Find path with zero heuristic (equivalent to Dijkstra) 使用零启发式函数查找路径（等同于Dijkstra）

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 | 最短路径的顶点列表

findPathWithCostLimit

public static <V> List<V> findPathWithCostLimit(Graph<V> graph,
 V source,
 V target,
 BiFunction<V,V,Double> heuristic,
 double maxCost)

Find path with cost limit 使用成本限制查找路径

Type Parameters:

V - the vertex type | 顶点类型

Parameters:

graph - the graph | 图

source - the source vertex | 源顶点

target - the target vertex | 目标顶点

heuristic - the heuristic function | 启发式函数

maxCost - maximum allowed path cost | 最大允许路径成本

Returns:

list of vertices in the path, or empty list if no path within cost | 路径的顶点列表，超出成本限制时返回空列表

findPathDetailed

public static <V> AStarUtil.PathResult<V> findPathDetailed(Graph<V> graph,
 V source,
 V target,
 BiFunction<V,V,Double> heuristic)

Find path with detailed result 查找路径并返回详细结果

Type Parameters:

V - the vertex type | 顶点类型

Parameters:

graph - the graph | 图

source - the source vertex | 源顶点

target - the target vertex | 目标顶点

heuristic - the heuristic function | 启发式函数

Returns:

detailed path result | 详细路径结果