Class ShortestPathUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.ShortestPathUtil
public final class ShortestPathUtil extends Object
Shortest Path Util 最短路径工具类

Utility class for shortest path algorithms.

最短路径算法的工具类。

Algorithms | 算法:

  • Dijkstra - Single-source shortest paths | 单源最短路径

Time Complexity | 时间复杂度: O((V+E)logV)

Space Complexity | 空间复杂度: O(V)

Features | 主要功能:

  • Dijkstra single-source shortest paths - Dijkstra单源最短路径
  • Shortest path reconstruction between two vertices - 两顶点间最短路径重建
  • Negative weight edge validation - 负权重边验证

Usage Examples | 使用示例:

// Get distances from source to all vertices
Map<String, Double> distances = ShortestPathUtil.dijkstra(graph, "A");

// Get shortest path between two vertices
List<String> path = ShortestPathUtil.shortestPath(graph, "A", "D");

Security | 安全性:

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

Performance | 性能特性:

  • Time complexity: O((V + E) log V) - 时间复杂度: O((V + 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:

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V> Map<V,Double>
    dijkstra(Graph<V> graph, V source)
    Dijkstra's algorithm for single-source shortest paths Dijkstra单源最短路径算法
    static <V> boolean
    hasPath(Graph<V> graph, V source, V target)
    Check if a path exists between two vertices 检查两个顶点之间是否存在路径
    static <V> double
    shortestDistance(Graph<V> graph, V source, V target)
    Get the shortest distance between two vertices 获取两个顶点之间的最短距离
    static <V> List<V>
    shortestPath(Graph<V> graph, V source, V target)
    Find shortest path between two vertices 查找两个顶点之间的最短路径

    Methods inherited from class Object

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

  • Method Details

    • dijkstra

      public static <V> Map<V,Double> dijkstra(Graph<V> graph, V source)
      Dijkstra's algorithm for single-source shortest paths Dijkstra单源最短路径算法
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      Returns:
      map of vertex to shortest distance from source | 从源顶点到各顶点的最短距离映射

    • shortestPath

      public static <V> List<V> shortestPath(Graph<V> graph, V source, V target)
      Find shortest path between two vertices 查找两个顶点之间的最短路径
      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 | 最短路径的顶点列表，无路径时返回空列表

    • shortestDistance

      public static <V> double shortestDistance(Graph<V> graph, V source, V target)
      Get the shortest distance between two vertices 获取两个顶点之间的最短距离
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      target - the target vertex | 目标顶点
      Returns:
      the shortest distance, or Double.MAX_VALUE if no path | 最短距离，无路径时返回Double.MAX_VALUE

    • hasPath

      public static <V> boolean hasPath(Graph<V> graph, V source, V target)
      Check if a path exists between two vertices 检查两个顶点之间是否存在路径
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      target - the target vertex | 目标顶点
      Returns:
      true if a path exists | 如果存在路径返回true